Submission #1005524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005524		ilef	Race (IOI11_race)	C++14	100 / 100	222 ms	34388 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
//const int MAX_N=2e5+14;
#define KK 1000001
int n,k;
int ans;
int mx_depth;
int cnt[KK];
bool removed[MAXN];
int subtree[MAXN];
vector<pair<int,int>>graph[MAXN];
int treesize(int node,int parent){
    subtree[node]=1;
    for(auto [w,child]:graph[node]){
        if(child!=parent && !removed[child]){

            subtree[node]+=treesize(child,node);
        }
    }

    return subtree[node];
}
int findcentroid(int node,int parent,int treesz){
    int sz=treesz/2;
    for(auto[w,child]:graph[node]){
        if(child!=parent && !removed[child]&& subtree[child]>(sz)){
            return findcentroid(child,node,treesz);
        }
    }
    return node;
}
void getans(int sum,int node,int parent,int depth,bool filling){
    if (sum>k){
        return;
    }

   // mx_depth=max(mx_depth,sum);
    if(filling==true){
        if(cnt[sum]==-1)cnt[sum]=depth;
        else{
    cnt[sum]=min(cnt[sum],depth);}
    }
    else{
        if(cnt[k-sum]!=-1){
            if(ans==-1){
                ans=depth+cnt[k-sum];
            }
            ans=min(ans,depth+cnt[k-sum]);
        }
    }
    for(auto[w,child]:graph[node]){
        if(child!=parent && ! removed[child]){
            getans(sum+w,child,node,depth+1,filling);
        }
    }
}
void del(int sum,int node,int p=-1){
    if(sum>k)return;
    cnt[sum]=-1;
    for(auto[w,child]:graph[node]){
        if(!removed[child]&& child!=p){
            del(sum+w,child,node);
        }
    }
}
void centroid_decomp(int node,int parent){

    int centroid=findcentroid( node, parent,treesize(node,parent));
    removed[centroid]=true;
    cnt[0]=0;
    for(auto &[w,child]:graph[centroid]){
            if(!removed[child]){
             getans(w,child,centroid,1,false);
            getans(w,child,centroid,1,true);
            }
    }

    //fill(cnt+1,cnt+mx_depth+1,inf);
    for(auto[w,i]:graph[centroid]){
        if(!removed[i]){
            del(w,i);
        }
    }
    for(auto[w,i]:graph[centroid]){
        if(!removed[i]){
        centroid_decomp(i,centroid);}
    }
}
int best_path(int N,int K,int H[][2],int L[]){
    mx_depth=0;
    n=N;
    k=K;
   // graph.resize(n);
    for(int i=0;i<n-1;i++){
        int u=H[i][0];
        int v=H[i][1];
        int w=L[i];
        graph[u].push_back({w,v});
        graph[v].push_back({w,u});
    }
    ans=-1;
    memset(cnt,-1,sizeof(cnt));
   // memset(removed,false,sizeof(removed));
    centroid_decomp(0,0);
   // if(ans>=inf)ans=-1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int treesize(int, int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto [w,child]:graph[node]){
      |              ^
race.cpp: In function 'int findcentroid(int, int, int)':
race.cpp:26:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto[w,child]:graph[node]){
      |             ^
race.cpp: In function 'void getans(int, int, int, int, bool)':
race.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto[w,child]:graph[node]){
      |             ^
race.cpp: In function 'void del(int, int, int)':
race.cpp:61:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto[w,child]:graph[node]){
      |             ^
race.cpp: In function 'void centroid_decomp(int, int)':
race.cpp:72:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto &[w,child]:graph[centroid]){
      |               ^
race.cpp:80:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto[w,i]:graph[centroid]){
      |             ^
race.cpp:85:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for(auto[w,i]:graph[centroid]){
      |             ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57