Submission #1087149

#TimeUsernameProblemLanguageResultExecution timeMemory
1087149quangminh412Race (IOI11_race)C++14
21 / 100
3072 ms20884 KiB
#include <bits/stdc++.h> using namespace std; /* John Watson https://codeforces.com/profile/quangminh98 Mua Code nhu mua Florentino !! */ #define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long const int maxn = 2e5 + 9; vector<int> adj[maxn]; int sz[maxn], par[20][maxn], h[maxn]; ll val[maxn], dist[maxn]; int n; ll k; void DFS(int u, int p = -1) { sz[u] = 1; for (int v : adj[u]) { if (v == p) continue; h[v] = h[u] + 1; par[0][v] = u; for (int i = 1; i < 20; i++) par[i][v] = par[i - 1][par[i - 1][v]]; DFS(v, u); sz[u] += sz[v]; } } int LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); int k = h[u] - h[v]; for (int i = 0; i < 20; i++) if (k >> i & 1) u = par[i][u]; if (u == v) return u; for (int i = 19; i >= 0; i--) if (par[i][u] != par[i][v]) { u = par[i][u]; v = par[i][v]; } return par[0][u]; } void DFS_compute(int u, int p = -1) { for (int v : adj[u]) { if (v == p) continue; dist[v] = dist[u] + val[v]; DFS_compute(v, 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++) { int u = H[i][0], v = H[i][1]; u++; v++; adj[u].push_back(v); adj[v].push_back(u); } DFS(1); for (int i = 0; i < n - 1; i++) { ll w = l[i]; int u = H[i][0], v = H[i][1]; u++; v++; val[h[u] > h[v] ? u : v] = w; } DFS_compute(1); int ans = 1e9; for (int u = 1; u <= n; u++) for (int v = u + 1; v <= n; v++) { int lca = LCA(u, v); if (dist[v] + dist[u] - 2 * dist[lca] == k) ans = min(ans, h[u] + h[v] - 2 * h[lca]); // cout << u - 1 << ' ' << v - 1 << ' ' << dist[v] + dist[u] - 2 * dist[lca] << '\n'; } return (ans == 1e9 ? -1 : 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...