Submission #133098

#TimeUsernameProblemLanguageResultExecution timeMemory
133098baluteshihRace (IOI11_race)C++14
100 / 100
615 ms39424 KiB
#include "race.h" #include <bits/stdc++.h> #define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define pb push_back #define ET cout << "\n" #define MEM(i,j) memset(i,j,sizeof i) #define F first #define S second #define MP make_pair #define ALL(v) v.begin(),v.end() #define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;} using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; bitset<200005> vis; vector<pii> G[200005]; const int INF=1e9; int ans=INF,k,wei,w[200005],tmp[1000005]; void center(int u,int f,int &cent,int sz) { int x=0; w[u]=1; for(pii i:G[u]) if(i.F!=f&&!vis[i.F]) center(i.F,u,cent,sz),x=max(x,w[i.F]),w[u]+=w[i.F]; x=max(x,sz-w[u]); if(x<wei) wei=x,cent=u; } void dfs(int u,int f,int d,int r,vector<pii> &v) { v.pb(MP(d,r)); for(pii i:G[u]) if(i.F!=f&&!vis[i.F]) dfs(i.F,u,d+i.S,r+1,v); } void cut(int u,int sz) { int c; wei=INF,center(u,u,c,sz); vis[c]=1; for(pii i:G[c]) if(!vis[i.F]) if(w[i.F]>w[c]) cut(u,w[u]-w[c]); else cut(i.F,w[i.F]); vector<int> rv; for(pii i:G[c]) if(!vis[i.F]) { vector<pii> v; dfs(i.F,i.F,i.S,1,v); for(pii j:v) if(j.F<=k&&tmp[k-j.F]!=INF) ans=min(ans,j.S+tmp[k-j.F]); for(pii j:v) if(j.F<=k) if(tmp[j.F]==INF) tmp[j.F]=j.S,rv.pb(j.F); else tmp[j.F]=min(tmp[j.F],j.S); } for(int i:rv) tmp[i]=INF; vis[c]=0; } int best_path(int N, int K, int H[][2], int L[]) { k=K,tmp[0]=0; for(int i=1;i<=K;++i) tmp[i]=INF; for(int i=0;i<N-1;++i) G[H[i][0]].pb(MP(H[i][1],L[i])),G[H[i][1]].pb(MP(H[i][0],L[i])); cut(0,N); if(ans==INF) return -1; return ans; }

Compilation message (stderr)

race.cpp: In function 'void cut(int, int)':
race.cpp:47:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(!vis[i.F])
     ^
race.cpp:60:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if(j.F<=k) 
       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...