Submission #1236049

#TimeUsernameProblemLanguageResultExecution timeMemory
1236049allin27xRace (IOI11_race)C++17
100 / 100
686 ms83008 KiB
#include <bits/stdc++.h> using namespace std; #define ll __int128 const int mod = 1e9+7; #define forn(i,n) for(int i=0; i<n; i++) #define readv(a,n) vector<int>a(n);forn(i,n)cin>>a[i]; #define readvv(a,n,m) vector<vector<int>> a(n,vector<int>(m));forn(i,n)forn(j,m)cin>>a[i][j]; #define all(a) a.begin(), a.end() #define _max(x,y) x = max(x,y) #define _min(x,y) x = min(x,y) // #define f first // #define s second const int MAXN = 2e5+5; const int MAXM = 1e6+5; vector<pair<int,int>> adj[MAXN]; int sbt[MAXN]; vector<int> ch[MAXN]; vector<pair<int,int>> inf[MAXN]; int pn[MAXM]; int rem[MAXN]; int mk[MAXN]; int par[MAXN]; void dfs(int i, int p) { sbt[i] = 1; for (auto [c, w]: adj[i]) { if (c==p || rem[c]) continue; dfs(c, i); sbt[i] += sbt[c]; } } int ctd(int i, int p, int sz) { for (auto [c,w] : adj[i]) { if (c==p || rem[c]) continue; if (2*sbt[c] > sz) return ctd(c, i, sz); } return i; } void calc(int i, int p, int dsw, int dse, int tp) { if (dsw >= MAXM) dsw = MAXM; if (i!=p) inf[tp]. push_back({dsw, dse}); for (auto [c,w]: adj[i]) { if (c==p || rem[c]) continue; calc(c, i, dsw+w, dse+1, tp); } } int build(int i) { dfs(i, 0); int x = ctd(i, i, sbt[i]); rem[x] = 1; for (auto [c,w] : adj[x]) { if (rem[c]) continue; ch[x].push_back(build(c)); par[ch[x].back()] = x; } return x; } int k; int ans = MAXM; void solve(int i) { inf[i].clear(); rem[i] = 1; for (auto [c,w]:adj[i]) { if (rem[c]) continue; int tp = c; while (par[tp] != i) tp = par[tp]; calc(c, i, w, 1, tp); } for (int c: ch[i]) { for (auto [dsw, dse]: inf[c]) { if (dsw >= MAXM) continue; pn[dsw] = MAXM; if (dsw <= k) pn[k-dsw] = MAXM; } } pn[0] = 0; for (int c: ch[i]) { for (auto [dsw, dse]: inf[c]) { if (dsw > k) continue; ans = min(ans, pn[k-dsw] + dse); } for (auto[dsw, dse]: inf[c]) { if (dsw > k) continue; pn[dsw] = min(pn[dsw], dse); } } for (int c: ch[i]) solve(c); } int best_path(int N, int K, int H[][2], int L[]) { k = K; for (int i=0; i<N-1; i++) { H[i][0] ++; H[i][1] ++; adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } int centr = build(1); for (int i=0; i<N+3; i++) rem[i] = 0; solve(centr); if (ans < MAXM)return ans; return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...