Submission #44345

#TimeUsernameProblemLanguageResultExecution timeMemory
44345shash42Race (IOI11_race)C++11
21 / 100
260 ms15604 KiB
#include<iostream> #include<vector> #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; vector< pii > adj[100005]; bool rem[100005]; int K, sub[100005], par[100005], nxt; int arr[1000005], best=1e9, ans=1e9, inf=1e9; vector< pii > q; void dfs1(int u) { sub[u]=1; for(pii v: adj[u]) { if(v.first!=par[u] && !rem[v.first]) { par[v.first]=u; dfs1(v.first); sub[u]+=sub[v.first]; } } } void dfs2(int u, int cand) { int currsz=sub[cand]-sub[u]; for(pii v: adj[u]) { if(v.first!=par[u] && !rem[v.first]) { currsz=max(currsz, sub[v.first]); dfs2(v.first, cand); } } if(currsz<best) { nxt=u; best=currsz; } } void dfs3(int u, int w, int l) { if(w>K) return; q.pb(mp(w, l)); for(pii v: adj[u]) { if(v.first!=par[u] && !rem[v.first]) { par[v.first]=u; dfs3(v.first, w+v.second, l+1); } } } void solve(int cent) { vector<int> tnow; tnow.pb(0); arr[0]=0; for(pii v: adj[cent]) { if(!rem[v.first]) { par[v.first]=cent; dfs3(v.first, v.second, 1); } for(int i = 0; i < q.size(); i++) { int w=q[i].first, l=q[i].second; if(w<=K) ans=min(ans, arr[K-w]+l); } for(int i = 0; i < q.size(); i++) { arr[q[i].first]=min(arr[q[i].first], q[i].second); tnow.pb(q[i].first); } q.clear(); } for(int i = 0; i < tnow.size(); i++) arr[tnow[i]]=inf; tnow.clear(); } void cent(int cand) { nxt=0; best=inf; par[cand]=cand; dfs1(cand); dfs2(cand, cand); solve(nxt); rem[nxt]=true; for(pii v: adj[nxt]) if(!rem[v.first]) cent(v.first); } int best_path(int n, int k, int h[][2], int l[]) { K=k; for(int i = 1; i <= n; i++) { adj[i].clear(); rem[i]=false; } for(int i = 0; i <= k; i++) arr[i]=inf; for(int i = 0; i < n-1; i++) { adj[h[i][0]].pb(mp(h[i][1], l[i])); adj[h[i][1]].pb(mp(h[i][0], l[i])); } cent(1); if(ans==inf) ans=-1; return ans; } /*int main() { int arr[][2]={{0, 1}, {1, 2}}; int lnt[]={1, 1}; cout << best_path(11, 12, arr, lnt); }*/

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < q.size(); i++)
                  ~~^~~~~~~~~~
race.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < q.size(); i++)
                  ~~^~~~~~~~~~
race.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tnow.size(); i++)
                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...