Submission #1167350

#TimeUsernameProblemLanguageResultExecution timeMemory
1167350SG2AlokRace (IOI11_race)C++20
0 / 100
2 ms4928 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second int sz[200005], mins[1000005]; bool vis[200005]; vector<pair<int, int>> adj[200005]; int ans = 1e9, k; int dfs(int u, int par){ if(vis[u]) return 0; sz[u] = 1; for(auto v: adj[u]){ if(v.fi != par){ sz[u] += dfs(v.fi, u); } } return sz[u]; } int ctr(int u, int par, int szz){ for(auto v: adj[u]){ if(v.fi == par) continue; if(!vis[v.fi] && sz[v.fi] * 2 > szz){ return ctr(v.fi, u, szz); } } return u; } void get_ans(int u, int par, int len, int dep){ if(len > k) return; ans = min(ans, mins[k - len] + dep); for(auto v: adj[u]){ if(!vis[v.fi] && v.fi != par){ get_ans(v.fi, u, len + v.se, dep + 1); } } } void dfs2(int u, int par, int len, int dep, int tp){ if(len > k) return; if(tp) mins[len] = min(mins[len], dep); else mins[len] = 1e9; for(auto v: adj[u]){ if(!vis[v.fi] && v.fi != par){ dfs2(v.fi, u, len + v.se, dep + 1, tp); } } } void ctr_dcmp(int u){ int cntr = ctr(u, -1, dfs(u, -1)); for(auto v: adj[cntr]){ if(!vis[v.fi]){ get_ans(v.fi, u, v.se, 1); dfs2(v.fi, u, v.se, 1, 1); } } for(auto v: adj[cntr]){ if(!vis[v.fi]){ dfs2(v.fi, u, v.se, 1, 0); } } vis[cntr] = true; for(auto v: adj[cntr]){ if(!vis[v.fi]){ ctr_dcmp(v.fi); } } } int best_path(int N, int K, int H[][2], int L[]){ k = K; for(int i = 0; i < N - 1; i++){ adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } for(int i = 1; i <= K; i++) mins[i] = 1e9; ctr_dcmp(1); 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...