Submission #428321

#TimeUsernameProblemLanguageResultExecution timeMemory
428321pliam경주 (Race) (IOI11_race)C++14
100 / 100
1809 ms51916 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 200005 #define INF (int)1e9 int ans; ll k; map<ll,int> existing,to_add;//(length, min number of edges) vector<pair<int,ll>> adj[MAXN];//(to,weight) bool rem[MAXN];//removed during centroid decomposition int size[MAXN]; int dfs_sz(int curr,int par=-1){//compute sizes size[curr]=1; for(auto p:adj[curr]){ int to=p.first; if(to==par||rem[to]) continue; size[curr]+=dfs_sz(to,curr); } return size[curr]; } int centroid(int curr,int par,int n){ for(auto p:adj[curr]){ int to=p.first; if(to==par||rem[to]) continue; if(size[to]>n/2) return centroid(to,curr,n); } return curr; } void dfs2(int curr,int par,int num,int len){//paths starting from curr if(to_add.count(len)) to_add[len]=min(to_add[len],num); else to_add[len]=num; //update ans if(existing.count(k-len)){ ans=min(ans,existing[k-len]+to_add[len]); } for(auto p:adj[curr]){ int to=p.first; ll w=p.second; if(to==par||rem[to]) continue; dfs2(to,curr,num+1,len+w); } } void build(int curr){ int n=dfs_sz(curr); int c=centroid(curr,-1,n); //find paths from c existing.clear(); to_add.clear(); existing[0]=0; for(auto p:adj[c]){ int to=p.first; ll w=p.second; if(rem[to]) continue; dfs2(to,c,1,w); //merge+clear to_add for(auto p_:to_add){ ll len=p_.first; int num=p_.second; if(existing.count(len)) existing[len]=min(existing[len],num); else existing[len]=num; } to_add.clear(); } //decompose rem[c]=true; for(auto p:adj[c]){ int to=p.first; if(!rem[to]) build(to); } } int best_path(int N, int K, int H[][2], int L[]) { ans=INF; k=K; for(int i=0;i<N;i++){ adj[i].clear(); } for(int i=0;i<N-1;i++){ int a=H[i][0]; int b=H[i][1]; ll w=L[i]; adj[a].push_back({b,w}); adj[b].push_back({a,w}); } memset(rem,false,sizeof(rem)); //centroid decomposition build(0); return ans==INF?-1:ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...