Submission #478716

#	Time	Username	Problem	Language	Result	Execution time	Memory
478716		byungkyu	Race (IOI11_race)	C++14	Compilation error	0 ms	0 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(N,K,H,L){     
    ll i,j,k,a,b,c,n;
    //scanf("%lld%lld",&n,&l);
    n=N;l=K;
    for(i=1;i<n;i++){
        //scanf("%lld%lld%lld",&a,&b,&c);
        //a++;b++;
        a=H[i][0];b=H[i][1];c=L[i][2];
        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:57:14: error: 'N' was not declared in this scope
   57 | ll best_path(N,K,H,L){
      |              ^
race.cpp:57:16: error: 'K' was not declared in this scope
   57 | ll best_path(N,K,H,L){
      |                ^
race.cpp:57:18: error: 'H' was not declared in this scope
   57 | ll best_path(N,K,H,L){
      |                  ^
race.cpp:57:20: error: 'L' was not declared in this scope
   57 | ll best_path(N,K,H,L){
      |                    ^
race.cpp:57:21: error: expression list treated as compound expression in initializer [-fpermissive]
   57 | ll best_path(N,K,H,L){
      |                     ^