Submission #746475

#TimeUsernameProblemLanguageResultExecution timeMemory
746475Sami_MassahRace (IOI11_race)C++17
100 / 100
482 ms84088 KiB
#include <bits/stdc++.h> using namespace std; const long long maxn = 2e5 + 12, mod = 998244353, inf = 1e9 + 12 ; long long n, k, ans = maxn, h[maxn], sz[maxn], cost[maxn], U[maxn], V[maxn], dist[maxn]; int H2[maxn][2], L2[maxn]; vector <int> conn[maxn]; map <int, int> mp[maxn]; bitset <maxn> marked; void dfs_set(int u){ marked[u] = 1; sz[u] = 1; for(int e: conn[u]){ int v = u ^ U[e] ^ V[e]; if(!marked[v]){ h[v] = h[u] + 1; dist[v] = dist[u] + cost[e]; dfs_set(v); sz[u] += sz[v]; } } } void dfs(int u, int p = -1){ marked[u] = 1; for(int e: conn[u]){ int v = u ^ U[e] ^ V[e]; if(!marked[v]){ dfs(v, u); if(mp[v].find(k + dist[u]) != mp[v].end()) ans = min(ans, mp[v][k + dist[u]] - h[u]); } } pair<long long, int> mx = make_pair(0, -1); for(int e: conn[u]){ int v = u ^ U[e] ^ V[e]; if(v != p) mx = max(mx, make_pair(sz[v], v)); } int f = mx.second; if(f != -1){ swap(mp[f], mp[u]); for(int e: conn[u]){ int v = u ^ U[e] ^ V[e]; if(v != p && v != f){ for(auto len: mp[v]){ if(mp[u].find(k + dist[u] * 2 - len.first) != mp[u].end()) ans = min(ans, mp[u][k + dist[u] * 2 - len.first] + len.second - 2 * h[u]); } for(auto len: mp[v]){ int x = mp[u][len.first]; if(x == 0) mp[u][len.first] = len.second; else mp[u][len.first] = min(x, len.second); } } } } long long x = mp[u][dist[u]]; if(x == 0) mp[u][dist[u]] = h[u]; else mp[u][dist[u]] = min(x, h[u]); } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; for(int i = 0; i < n - 1; i++){ cost[i] = L[i]; U[i] = H[i][0]; V[i] = H[i][1]; conn[U[i]].push_back(i); conn[V[i]].push_back(i); } // cout << n << ' ' << k << endl; dfs_set(1); marked = 0; dfs(1); if(ans == maxn) ans = -1; return ans; } /* int main(){ int N, K; cin >> N >> K; for(int i = 0; i < N - 1; i++) cin >> H2[i][0] >> H2[i][0]; for(int i = 0; i < N - 1; i++) cin >> L2[i]; cout << best_path(N, K, H2, L2) << endl; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...