Submission #1209813

#TimeUsernameProblemLanguageResultExecution timeMemory
1209813nvc2k8Race (IOI11_race)C++20
100 / 100
622 ms38204 KiB
#include <bits/stdc++.h> #include "race.h" #define TASK "race" #define INT_LIM (int) 2147483647 #define LL_LIM (long long) 9223372036854775807 #define endl '\n' #define mp make_pair #define pb push_back #define fi first #define se second #define BIT(i,x) (((i)>>(x))&1) #define FOR(i,a,b) for(int i = (a); i<=(b); i++) #define FORD(i,a,b) for(int i = (a); i>=(b); i--) #define ll long long #define pii pair<int,int> using namespace std; ///------------------------------------------/// int n,k, ans = INT_LIM; vector<pii> adj[200005]; bool dis[200005]; int sz[200005]; void initsize(int u, int p) { sz[u] = 1; for (auto V:adj[u]) if (V.fi!=p && !dis[V.fi]) { initsize(V.fi, u); sz[u]+= sz[V.fi]; } } int findcentroid(int u, int p, int n) { for (auto V:adj[u]) if (V.fi!=p && !dis[V.fi] && sz[V.fi]>n/2) { return findcentroid(V.fi, u, n); } return u; } map<int,int> f; void dfs(int u, int p, int deep, int d, bool upd) { if (d>k) return; if (!upd) { if (f.find(k-d)!=f.end()) { ans = min(ans, f[k-d]+deep); } } else { if (f.find(d)!=f.end()) f[d] = min(f[d], deep); else f[d] = deep; } for (auto V:adj[u]) if (V.fi!=p && !dis[V.fi]) { int v = V.fi, w = V.se; dfs(v, u, deep+1, d+w, upd); } } void process(int u) { f.clear(); f[0] = 0; for (auto V:adj[u]) if (!dis[V.fi]) { int v = V.fi, w = V.se; dfs(v, u, 1, w, 0); dfs(v, u, 1, w, 1); } } void decompose(int u) { initsize(u, -1); u = findcentroid(u, -1, sz[u]); process(u); dis[u] = true; for (auto V:adj[u]) if (!dis[V.fi]) { decompose(V.fi); } } int best_path(int N, int K, int h[][2], int l[]) { n = N; k = K; FOR(i, 0, n-2) { int u = h[i][0]+1, v = h[i][1]+1; adj[u].pb(mp(v,l[i])); adj[v].pb(mp(u,l[i])); } decompose(1); if (ans==INT_LIM) return -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...