Submission #1166126

#TimeUsernameProblemLanguageResultExecution timeMemory
1166126duccnamm경주 (Race) (IOI11_race)C++20
43 / 100
3094 ms30296 KiB
#include<bits/stdc++.h> #include "race.h" using namespace std; #define ll int ll n,m,u,v,w,child[200005],f[200005],ans,d; vector<pair<ll,ll>>a[200005]; bool del[200005]; unordered_map<ll,ll>mp; vector<pair<ll,ll>>vc; void dfsmake(ll x,ll pa) { child[x]=1; for(pair<ll,ll> it:a[x]) if(del[it.first]==0&&it.first!=pa) { dfsmake(it.first,x); child[x]+=child[it.first]; } } ll getcentroid(ll x,ll pa,ll n) { for(pair<ll,ll> it:a[x]) if(it.first!=pa&&del[it.first]==0&&child[it.first]>n/2) return getcentroid(it.first,x,n); return x; } void dfsgetans(ll x,ll pa,ll dist) { // cout<<d<<" "<<m-d<<'\n'; if(m-d<0) return; vc.push_back({d,dist}); // cout<<m-d<<" "<<d<<" "<<mp[m-d]<<' '<<dist<<'\n'; if(m-d==0) ans=min(ans,dist); else if(mp[m-d]!=0) ans=min(ans,dist+mp[m-d]); for(pair<ll,ll> it:a[x]) if(it.first!=pa&&del[it.first]==0) { d+=it.second; dfsgetans(it.first,x,dist+1); d-=it.second; } } void dfscentroid(ll x,ll pa) { dfsmake(x,0); ll u=getcentroid(x,0,child[x]); for(pair<ll,ll> it:a[u]) if(del[it.first]==0) { d=it.second; dfsgetans(it.first,u,1); for(pair<ll,ll>it:vc) { if(mp[it.first]==0) mp[it.first]=it.second; else mp[it.first]=min(mp[it.first],it.second); } vc.clear(); } mp.clear(); // cout<<u<<" "<<ans<<'\n'; del[u]=1; for(pair<ll,ll> it:a[u]) if(del[it.first]==0) dfscentroid(it.first,u); } int best_path(int N,int M,int H[][2],int L[]) { m=M; n=N; for(int i=0;i<=n-2;i++) { u=H[i][0]+1; v=H[i][1]+1; w=L[i]; // cout<<u<<" "<<v<<" "<<w<<'\n'; a[u].push_back({v,w}); a[v].push_back({u,w}); } ans=1e9; dfscentroid(1,0); if(ans!=1e9) return ans; return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...