Submission #1020613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020613		doducanh	Race (IOI11_race)	C++14	100 / 100	659 ms	41560 KiB

race

#include <bits/stdc++.h>

using namespace std;
#define ii pair<int,int>
const int maxn=2e5+7;
int removed[maxn];
int subtree[maxn];
vector<int> cnt(1e6+7,-1);
vector<ii>a[maxn];
set<int>s;
int n,k;
int res=1e9+7;
int get_subtree(int u,int par){
    subtree[u]=1;
    for(auto [v,C]:a[u]){
        if(v==par||removed[v])continue;
        subtree[u]+=get_subtree(v,u);
    }
    return subtree[u];
}
int get_cen(int u,int par,int treesize){
    for(auto [v,C]:a[u]){
        if(removed[v]||v==par)continue;
        if((subtree[v]<<1)>treesize)return get_cen(v,u,treesize);
    }
    return u;
}
void get_cnt(int u,int par,bool filling,int sum,int depth=1){
    if(sum>k)return;
    if(filling){
        if(cnt[k-sum]!=-1){
            res=min(res,depth+cnt[k-sum]);
        }
    }
    else{
        s.insert(sum);
        if(cnt[sum]!=-1)cnt[sum]=min(cnt[sum],depth);
        else cnt[sum]=depth;

    }
    for(auto [v,C]:a[u]){
        if(v==par||removed[v])continue;
        get_cnt(v,u,filling,sum+C,depth+1);
    }
}
void centroid_decomp(int u=0){

    int c=get_cen(u,0,get_subtree(u,0));
    removed[c]=1;
    for(auto [v,C]:a[c]){
        if(removed[v]==0){
            get_cnt(v,c,true,C);
            get_cnt(v,c,false,C);
        }
    }
    for(int x:s)cnt[x]=-1;
    s.clear();
    for(auto [v,C]:a[c]){
        if(removed[v]==0){
            centroid_decomp(v);
        }
    }
}
void solve()
{
    cnt[0]=0;
    centroid_decomp();
    if(res==1e9+7){res=-1;}
}
int best_path(int N,int K,int H[][2],int L[]){
//    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    n=N;
    k=K;
    for(int i=0;i<n-1;i++){
        int x=H[i][0];
        int y=H[i][1];
        int w=L[i];
        a[x].push_back({y,w});
        a[y].push_back({x,w});
    }
    solve();
    return res;
}

Compilation message (stderr)

race.cpp: In function 'int get_subtree(int, int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto [v,C]:a[u]){
      |              ^
race.cpp: In function 'int get_cen(int, int, int)':
race.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [v,C]:a[u]){
      |              ^
race.cpp: In function 'void get_cnt(int, int, bool, int, int)':
race.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [v,C]:a[u]){
      |              ^
race.cpp: In function 'void centroid_decomp(int)':
race.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [v,C]:a[c]){
      |              ^
race.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [v,C]:a[c]){
      |              ^

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