Submission #871989

#	Time	Username	Problem	Language	Result	Execution time	Memory
871989		Warinchai	Race (IOI11_race)	C++14	100 / 100	323 ms	106016 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >adj[200005];
int sz[200005];
int used[200005];
long long cnt[1000005];
int inf=1e9;
long long ans=inf;
vector<pair<int,long long> >v[200005];
int n,k;
int dfssz(int u,int p=-1){
    sz[u]=1;
    for(auto x:adj[u])if(!used[x.first]&&x.first!=p)sz[u]+=dfssz(x.first,u);
    return sz[u];
}
int centroid(int u,int rsz,int p=-1){
    for(auto x:adj[u])if(!used[x.first]&&x.first!=p&&sz[x.first]>rsz/2)return centroid(x.first,rsz,u);
    return u;
}
void dfs1(int u,int d,int l,int rt,int p=-1){
    if(d<=k)v[rt].push_back({d,l});else return;
    for(auto x:adj[u])if(!used[x.first]&&x.first!=p)dfs1(x.first,d+x.second,l+1,rt,u);
}
void decom(int u){
    u=centroid(u,dfssz(u));
    //cerr<<"u:"<<u<<endl;
    used[u]=1;
    for(auto x:adj[u])if(!used[x.first]){
        dfs1(x.first,x.second,1,x.first);
        for(auto d:v[x.first])if(d.first<=k)ans=min(ans,cnt[k-d.first]+d.second);
        for(auto d:v[x.first])if(d.first<=k)cnt[d.first]=min(cnt[d.first],d.second);
    }
    for(auto x:adj[u])if(!used[x.first]){
        for(auto d:v[x.first])if(d.first<=k)cnt[d.first]=inf;
        v[x.first].clear();
    }
    for(auto x:adj[u])if(!used[x.first])decom(x.first);
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }
    for(int i=0;i<=K;i++)cnt[i]=inf;
    cnt[0]=0;
    decom(1);
    return ans==inf?-1:ans;
}

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