Submission #1186185

#TimeUsernameProblemLanguageResultExecution timeMemory
1186185nikaa123경주 (Race) (IOI11_race)C++20
43 / 100
3094 ms66180 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #include "race.h" #include <bits/stdc++.h> using namespace std; // #define ll long long #define pb push_back #define endl '\n' #define ff first #define ss second typedef vector<int> vii; typedef pair<int,int> pii; const int inf = INT_MAX; const int N = 2e5 + 5; int n,k,a,b,c; map <pii,int> l; int sz[N],fix[N],dead[N]; vector <vii> v(N); int s,u; int len; vector <vii> lst(N); int ans; vector <int> A; void dfs(int x) { sz[x] = 1; fix[x] = 1; for (auto to:v[x]) { if (!fix[to] && !dead[to]) { dfs(to); sz[x] += sz[to]; } } } void dfs1(int x) { s++; fix[x] = 1; for (auto to:v[x]) { if (!dead[to] && !fix[to]) { dfs1(to); } } } int dfs2(int x, int p) { for (auto to:v[x]) { if (dead[to] || to == p) continue; if (sz[to] > s/2) return dfs2(to,x); } return x; } void dfs3(int x, int p, int len,int d,vector <pii> &lst) { if (len > k) return; lst.pb({len,d}); for (auto to:v[x]) { if (dead[to] || to == p) continue; dfs3(to,x,len+l[{to,x}],d+1,lst); } } void solve(int u) { A = vector <int>(k+1,inf); A[0] = 0; for (auto lw:v[u]) { if (dead[lw]) continue; vector <pii> lst; dfs3(lw,u,l[{lw,u}],1,lst); for (auto l:lst) { if (l.ff > k) continue; if (A[k-l.ff] != inf) ans = min(ans,l.ss+A[k-l.ff]); } for (auto l:lst) { if (l.ff > k) continue; A[l.ff] = min(A[l.ff],l.ss); } } } int best_path(int N, int K, int H[][2], int L[]) { n=N; k = K; for (int i = 0; i < n-1; i++) { a = H[i][0]; b = H[i][1]; c = L[i]; v[a].pb(b); v[b].pb(a); l[{a,b}] = c; l[{b,a}] = c; } bool ok = true; ans = inf; while (ok) { ok = false; for (int i = 0; i < n; i++) { fix[i] = 0; sz[i] = 0; } for (int i = 0; i < n; i++) { if (!fix[i] && !dead[i]) dfs(i); } for (int i = 0; i < n; i++) { fix[i] = 0; } for (int i = 0; i < n; i++) { if (!fix[i] && !dead[i]) { s = 0; dfs1(i); u = dfs2(i,-1); if (s > 1) { ok = true; solve(u); dead[u] = 1; } } } } if (ans == inf) 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...