Submission #109581

#TimeUsernameProblemLanguageResultExecution timeMemory
109581ErkhemkhuuRace (IOI11_race)C++17
43 / 100
3106 ms46552 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define F first #define S second vector <pair <int, int> > adj[200005]; map <int, int> global_path, local_path; bool isCentroid[200005] = {false}; int subtr_size[200005], localCentroid, k, ans; inline void SubTreeSize(int v, int p) { subtr_size[v] = 1; for(auto &it: adj[v]) if(it.F != p && !isCentroid[it.F]) { SubTreeSize(it.F, v); subtr_size[v] += subtr_size[it.F]; } return; } inline void traverse(int v, int p, int w, int l) { if(w > k) return; if(w == k) ans = min(ans, l); int temp = global_path[k - w]; if(temp) ans = min(ans, l + temp); if(!local_path[w] || local_path[w] > l) local_path[w] = l; for(auto &it: adj[v]) if(it.F != p && !isCentroid[it.F]) traverse(it.F, v, w + it.S, l + 1); return; } inline void findCentroid(int v, int p, int size) { bool flag = (size - subtr_size[v] <= size / 2); for(auto &it: adj[v]) if(it.F != p && !isCentroid[it.F]) { flag &= (subtr_size[it.F] <= size / 2); findCentroid(it.F, v, size); } if(flag) localCentroid = v; return; } inline void go(int v) { SubTreeSize(v, -1); findCentroid(v, -1, subtr_size[v]); global_path.clear(); isCentroid[localCentroid] = true; for(auto &it: adj[localCentroid]) if(!isCentroid[it.F]) { local_path.clear(); traverse(it.F, localCentroid, it.S, 1); for(auto &localit: local_path) if(!global_path[localit.F] || global_path[localit.F] > localit.S) global_path[localit.F] = localit.S; } for(auto &it: adj[localCentroid]) if(!isCentroid[it.F]) go(it.F); return; } int best_path(int N, int K, int H[][2], int L[]) { int i; k = K; for(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])); } ans = 1e9; go(0); if(ans == 1e9) ans = -1; return 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...