Submission #478718

#	Time	Username	Problem	Language	Result	Execution time	Memory
478718		byungkyu	Race (IOI11_race)	C++14	43 / 100	769 ms	47944 KiB

race

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

ll getsz(ll n,ll 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];
}

ll getcent(ll now,ll pa,ll cap){
    ll 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;
}

ll adjmax(ll now,ll pa){
    ll 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(ll now,ll pa,ll th,ll w,ll 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);
    }
    dp[w]=dis;
}

ll best_path(int N,int K,int H[][2],int L[]){     
    ll 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;
            //printf("new %lld %lld\n",i,t.fi);
            dfs(t.fi,i,cent[i],t.se,1);
        }
        while(st.size()){
            dp[st.back()]=-1;
            st.pop_back();
        }
    }
    if(ret==1e6)return -1;
    return ret;
}

Compilation message (stderr)

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

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