| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 471666 | NicolaAbusaad2014 | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/** * Prof.Nicola**/#include <bits/stdc++.h> using namespace std;#define endl "\n"#define mp make_pair#define F first#define S second#define REP(i,l,r) for(long long i=(l);i<(r);i++)#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)long k,ans=1e9;vector<long long>len;vector<pair<pair<long,long>,pair<long,long> > >mn;struct tree{ long long n; vector<vector<pair<long,long> > >edges; vector<long>depth,sz; vector<bool>vis; void scan0(long x,long p,long long l) { len[x]=l; depth[x]=depth[p]+1; sz[x]=1; REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan0(edges[x][i].F,x,l+edges[x][i].S); sz[x]+=sz[edges[x][i].F]; } } void scan(long x,long p,long long l,long h) { if(l>k){ return; } if(depth[x]<=mn[l].F.F){ if(mn[l].F.S==h){ mn[l].F.F=depth[x]; } else{ mn[l].S=mn[l].F; mn[l].F=mp(depth[x],h); } } else if(depth[x]<mn[l].S.F){ if(mn[l].F.S!=h){ mn[l].S=mp(depth[x],h); } } REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan(edges[x][i].F,x,l+edges[x][i].S,h); } } void scan2(long x,long p,long long l,long h) { if(l>k){ return; } if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){ ans=min(ans,depth[x]+mn[k-l].S.F); } else if(h!=mn[k-l].F.S){ ans=min(ans,depth[l]+mn[k-l].F.F); } REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan2(edges[x][i].F,x,l+edges[x][i].S,h); } } void scan3(long x,long p,long long l,long h) { if(l>k){ return; } mn[l]=mp(mp(1e9,0),mp(1e9,0)); REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan3(edges[x][i].F,x,l+edges[x][i].S,h); } } long centroid(long x,long p,long z) { long mx=0,node=x; REP(i,0,edges[x].size()){ if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){ mx=sz[edges[x][i].F]; node=edges[x][i].F; } } if(mx<z){ return x; } return centroid(node,x,z); } void read(long nodes,vector<vector<pair<long,long> > >e) { n=nodes; edges=e; } void build(long long root=1) { vis.clear(); vis.resize(n+1); depth.clear(); depth.resize(n+1); depth[0]=0; sz.clear(); sz.resize(n+1); scan0(root,0,0); }};tree t;void solve(long x){ t.scan0(x,0,0); x=t.centroid(x,0,(t.sz[x]+1)/2); t.vis[x]=true; REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan0(t.edges[x][i].F,0,t.edges[x][i].S); t.scan(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan2(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan3(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } solve(t.edges[x][i].F); }}int best_path(int N, int K, int H[][2], int L[]){ mn.resize(K+1); mn[0]=mp(mp(0,1),mp(0,2)); REP(i,1,K){ mn[i]=mp(mp(1e9,0),mp(1e9,0)); } k=K; len.resize(N+1); vector<vector<pair<long,long> > >e(N+1); REP(i,0,N-1){ e[H[i][0]+1].push_back(mp(H[i][1]+1,L[i])); e[H[i][1]+1].push_back(mp(H[i][0]+1,L[i])); } t.read(N,e); t.build(); solve(1); if(ans>=999999998){ return -1; } return ans;}