Submission #1004548

#TimeUsernameProblemLanguageResultExecution timeMemory
1004548GrayRace (IOI11_race)C++17
0 / 100
2 ms2908 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; 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, set<pair<ll, ll>> &usg, ll level, ll dep){ usg.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, usg, level+e[i].ff, dep+1); } } void cedfs(ll u, ll &mn, ll wsz){ ll centr = -1; findcentroid(u,u, 0, centr, wsz); // assert(centr!=-1); set<pair<ll, ll>> levs, full; 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, levs, 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 = 2e18; cedfs(0, mn, getsz(0, 0)); return (mn==2e18?-1:mn); }

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:88:11: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   88 |   ll mn = 2e18;
      |           ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...