Submission #1004558

#TimeUsernameProblemLanguageResultExecution timeMemory
1004558GrayRace (IOI11_race)C++17
21 / 100
3047 ms20928 KiB
#include<bits/stdc++.h> #include "race.h" using namespace std; #define ll int #define ff first #define ss second #define ln "\n" vector<pair<ll, pair<ll, ll>>> e; vector<vector<ll>> A; vector<bool> black; vector<ll> sz; set<pair<ll, ll>> levs, full; ll n, k; ll getsz(ll u, ll p){ sz[u]=1; for (auto i:A[u]){ if (black[i]) continue; ll v = e[i].ss.ff^e[i].ss.ss^u; if (v==p) continue; sz[u]+=getsz(v, u); } return sz[u]; } void findcentroid(ll u, ll p, ll up, ll &centr, ll wsz){ for (auto i:A[u]){ if (black[i]) continue; ll v = e[i].ss.ff^e[i].ss.ss^u; if (v==p) continue; if (sz[v]>wsz/2) {findcentroid(v, u, up+1, centr, wsz); return;} } centr=u; return; } void dfs(ll u, ll p, ll level, ll dep){ levs.insert({level, dep}); for (auto i:A[u]){ ll v = e[i].ss.ff^e[i].ss.ss^u; if (v==p or black[i]) continue; dfs(v, u, level+e[i].ff, dep+1); } } void cedfs(ll u, ll &mn, ll wsz){ levs.clear(); full.clear(); ll centr = -1; findcentroid(u,u, 0, centr, wsz); // assert(centr!=-1); for (auto i:A[u]){ if (black[i]) continue; ll v = e[i].ss.ff^e[i].ss.ss^u; levs.clear(); dfs(v, u, e[i].ff, 1); for (auto [length, tim]:levs){ auto it = full.lower_bound({k-length, -1}); if (!full.empty() and it!=full.end() and (*it).ff==k-length){ mn=min(mn, tim+(*it).ss); } if (length==k) { mn=min(mn, tim); } } // cout << ln; for (auto [length, tim]:levs){ full.insert({length, tim}); } } for (auto i:A[u]){ if (black[i]) continue; black[i]=1; ll v = e[i].ss.ff^e[i].ss.ss^u; cedfs(v, mn, getsz(v, v)); } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k=K; e.resize(N-1); A.resize(N); for (ll i=0; i<n-1; i++){ A[H[i][0]].push_back(i); A[H[i][1]].push_back(i); e[i] = {L[i], {H[i][0], H[i][1]}}; } black.resize(N); sz.resize(N); ll mn = n+1; cedfs(0, mn, getsz(0, 0)); return (mn==n+1?-1:mn); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...