Submission #478714

#	Time	Username	Problem	Language	Result	Execution time	Memory
478714		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;
}

void solve(){     
    ll i,j,k,a,b,c,n;
    scanf("%lld%lld",&n,&l);
    for(i=1;i<n;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        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)printf("-1");
    else printf("%lld\n",ret);
}

int main(){
    int T=1;
    freopen("grader.in.1","r",stdin);
    //scanf("%d",&T);
    while(T--){
        solve();
    }
} 

Compilation message (stderr)

race.cpp: In function 'void solve()':
race.cpp:58:10: warning: unused variable 'j' [-Wunused-variable]
   58 |     ll i,j,k,a,b,c,n;
      |          ^
race.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%lld%lld",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
race.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen("grader.in.1","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cchvmB3q.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccaai8Is.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccaai8Is.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status