Hint 1:

Hint 2:

Hint 3:

Hint 4:

Hint 5:

Ususally in Competitive programming tasks are designed so that you are able to solve them in any structure you would like to. What I mean that it doesn't matter what linear data structure you use, all of them would be able to get the problem. But sometimes if the intended solution is to use linear memory, you won't be able to have quadratic consumption in your code. So don't worry, Alot of topcoders use only STL structures (vector for example) instead of arrays.

First of all check this

Centroid Decomposition in Trees Tutorial

Actually IOI Race is a simple application of centroid decomposition

After that you may check this problem for implementation of centroid

Codeforces 321C: Ciel The Commander

After doing this you may tell me if you still have problems

Hint 1:

Hint 2:

Hint 3:

Hint 4:

#include <bits/stdc++.h>
 
using namespace std;
const long long MX = (1<<20);
 
int main(){
    int T;
    cin>>T;
    while(T--){
        priority_queue < pair < long long , long long > > Q;
        long long ans = 0;
        long long n;
        long long tosell = 0;
        cin>>n;
        for(long long j = 1 ; j <= n ; j++){
            long long income , price , lim;
            scanf("%lld %lld %lld",&income,&price,&lim);
            tosell += income;
            //calculate current excess
            long long sell = min(lim , tosell);
            //sell as much of current unselled share
            lim -= sell;
            tosell -= sell;
 

#include <bits/stdc++.h>
#define P(x,y) make_pair(x,y)
using namespace std;
const int MX=(1<<17);
vector < pair < int , int > > v[MX];
int T , n , sz[MX];
long double ans , coef;
void dfs(int x , int p){
    sz[x]=1;
    for(auto pp : v[x]){
        int nxt = pp.first;
        if(nxt == p) continue;
        dfs(nxt , x);
        sz[x]+=sz[nxt];
        long double theta = pp.second;
        theta *= (sz[nxt]) * (n-sz[nxt]);
        theta/=coef;
        ans+=theta;
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif // ONLINE_JUDGE

Hint 1:

Answer is equal to :

Calculating the distance between every pairs of nodes is a solution that will get TLE for sure. Let's try to think of a better solution. Observe that each edge would be included in the distance of each pair of nodes such that this is edge is a part of the path between them. So let's write our answer in another way.

Hint 2:

Hint 3:

#include<bits/stdc++.h>
using namespace std;
const long long MX=(1<<20);
bool dp[MX+1];
long long n ,arr[31] , m , x;
set < long long > S;
int main(){
    #ifdef ONLINE_JUDGE
    freopen("key.in","r",stdin);
    freopen("key.out","w",stdout);
    #endif // ONLINE_JUDGE
    cin>>n>>m;
    long long sum=0;
    for(long long j=1;j<=n;j++) cin>>arr[j];
    sort(arr+1 , arr+1+n);
    for(long long j=1;j<=n && m > 0;j++){
        if(arr[j] == sum+1){
            sum+=arr[j];
            continue;
        }
        if(arr[j] > sum){
            cout<<sum+1<<' ';
            j--;
            sum+=sum+1;

Hint 1:

Hint 2:

Hint 3:

Hint 4:

#include <bits/stdc++.h>
 
using namespace std;
const int MX = (1<<20);
pair < int , int > exam[MX];
priority_queue < pair < int , int > > Q;
int ans[MX];
int main(){
    int n;
    scanf("%d",&n);
    for(int j = 1 ; j <= n ; j++){
        scanf("%d %d",&exam[j].first,&exam[j].second);
    }
    int rem = n , it = 1 , flag = 0;
    for(int day = 1 ; rem > 0 ; day++){
        while(it <= n && exam[it].first == day){
            Q.push({exam[it].second - flag , it});
            ++it;
        }
        if(!Q.empty()){
            ans[Q.top().second] = day; Q.pop();
            --rem;
        }
        ++flag;