Submission #1210310

#TimeUsernameProblemLanguageResultExecution timeMemory
1210310Born_To_LaughRace (IOI11_race)C++17
43 / 100
536 ms82272 KiB
// Born_To_Laugh - Hughie Do #include <bits/stdc++.h> #define alle(Lotus) Lotus.begin(), Lotus.end() using namespace std; typedef long long ll; [[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7; #define int ll const int maxn = 2e5 + 5; int n, k; int ans = INF; vector<int> sz(maxn, 1), bigchild(maxn, -1), dep(maxn, 0), dist(maxn, 0); vector<int> adj[maxn]; map<pair<int,int>, int> wei; map<int,int> mp; void pre_dfs(int a, int par){ for(auto &elm: adj[a]){ if(elm == par)continue; dep[elm] = dep[a] + 1; dist[elm] = dist[a] + wei[{a, elm}]; pre_dfs(elm, a); sz[a] += sz[elm]; if(bigchild[a] == -1 || sz[bigchild[a]] < sz[elm])bigchild[a] = elm; } } //dist[1] + dist[2] - 2*dist[lca] = k //dep[1] + dep[2] - 2*dep[lca]; void add(int a, int par, bool godown, int distlca, int deplca){ int dist1 = k + 2 * distlca - dist[a]; if(mp.find(dist1) != mp.end()){ ans = min(ans, mp[dist1] + dep[a] - 2*deplca); } if(mp.find(dist[a]) == mp.end()) mp[dist[a]] = dep[a]; else mp[dist[a]] = min(mp[dist[a]], dep[a]); if(!godown)return; for(auto &elm: adj[a]){ if(elm == par)continue; add(elm, a, 1, distlca, deplca); } } void dfs(int a, int par, bool keep){ for(auto &elm: adj[a]){ if(elm == par || elm == bigchild[a])continue; dfs(elm, a, 0); } if(bigchild[a] != -1) dfs(bigchild[a], a, 1); add(a, par, 0, dist[a], dep[a]); for(auto &elm: adj[a]){ if(elm == par || elm == bigchild[a])continue; add(elm, a, 1, dist[a], dep[a]); } if(!keep)mp.clear(); } int best_path(signed N, signed K, signed H[][2], signed L[]){ n = N; k = K; for(int i=0; i<n-1; ++i){ int x = H[i][0], y = H[i][1]; adj[x].push_back(y); adj[y].push_back(x); int w = L[i]; wei[{x, y}] = w; wei[{y, x}] = w; } pre_dfs(0, -1); dfs(0, -1, 1); 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...