Submission #478734

#	Time	Username	Problem	Language	Result	Execution time	Memory
478734		byungkyu	Race (IOI11_race)	C++14	100 / 100	1035 ms	43348 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
 
vector<pii> ch[200005],vec;
vector<int> st;
set<int> se;
int sz[200005],cent[200005],dp[1000005],ret=1e6,l;

int getsz(int n,int pa){
    sz[n]=1;
    for(auto a : ch[n]){
        if(a.fi==pa||cent[a.fi])continue;
        sz[n]+=getsz(a.fi,n);
    }
    return sz[n];
}

int getcent(int now,int pa,int cap){
    int b,m=cap-sz[now];
    for(auto a : ch[now]){
        if(a.fi==pa||cent[a.fi])continue;
        m=max(m,sz[a.fi]);
        b=getcent(a.fi,now,cap);
        if(b)return b;
    }
    if(m*2<=cap)return now;
    return 0;
}

int adjmax(int now,int pa){
    int k=0;
    for(auto a : ch[now]){
        if(a.fi==pa)continue;
        if(cent[a.fi])k=max(k,cent[a.fi]);
        else k=max(k,adjmax(a.fi,now));
    }
    return k;
}

void dfs(int now,int pa,int th,int w,int dis){
    if(w>l)return;
    st.push_back(w);
    if(l>=w&&dp[l-w]!=-1)ret=min(ret,dp[l-w]+dis);
    for(auto a : ch[now]){
        if(a.fi==pa)continue;
        if(cent[a.fi]<=th)continue;
        dfs(a.fi,now,th,w+a.se,dis+1);
    }
    vec.push_back({w,dis});
}

int best_path(int N,int K,int H[][2],int L[]){     
    int i,j,k,a,b,c,n;
    //scanf("%lld%lld",&n,&l);
    n=N;l=K;
    for(i=0;i<n-1;i++){
        //scanf("%lld%lld%lld",&a,&b,&c);
        //a++;b++;
        a=H[i][0];b=H[i][1];c=L[i];
        a++;b++;
        ch[a].push_back({b,c});
        ch[b].push_back({a,c});
    }
    for(i=1;i<=n;i++){
        se.insert(i);
    }
    while(!se.empty()){
        a=*se.begin();
        k=getsz(a,0);
        b=getcent(a,0,k);
        cent[b]=adjmax(a,0)+1;
        //printf("%lld %lld\n",b,cent[b]);
        se.erase(se.find(b));
    }
    for(i=1;i<=l;i++)dp[i]=-1;
    for(i=1;i<=n;i++){
        for(auto t : ch[i]){
            if(cent[t.fi]<=cent[i])continue;
            dfs(t.fi,i,cent[i],t.se,1);
            while(vec.size()){
                if(dp[vec.back().fi]==-1)dp[vec.back().fi]=vec.back().se;
                else dp[vec.back().fi]=min(dp[vec.back().fi],vec.back().se);
                vec.pop_back();
            }
        }
        while(st.size()){
            dp[st.back()]=-1;
            st.pop_back();
        }
    }
    if(ret==1e6)return -1;
    return ret;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:58:11: warning: unused variable 'j' [-Wunused-variable]
   58 |     int i,j,k,a,b,c,n;
      |           ^

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