제출 #1128895

#제출 시각아이디문제언어결과실행 시간메모리
1128895viwlesxq경주 (Race) (IOI11_race)C++20
21 / 100
3096 ms18500 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 1; const int inf = 1e9; int d[N], dp[N], up[N][18]; int tin[N], tout[N], timer; vector<array<int, 2>> g[N]; void dfs(int v, int p = 0) { tin[v] = ++timer; up[v][0] = p; for (int i = 1; i < 18; ++i) up[v][i] = up[up[v][i - 1]][i - 1]; for (auto [to, w] : g[v]) { if (to != p) { d[to] = d[v] + 1; dp[to] = dp[v] + w; dfs(to, v); } } tout[v] = ++timer; } bool upper(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v) { if (upper(u, v)) return u; if (upper(v, u)) return v; for (int i = 17; i >= 0; --i) if (!upper(up[u][i], v)) u = up[u][i]; return up[u][0]; } int get(int u, int v, int k) { int p = lca(u, v); if (dp[u] + dp[v] - 2 * dp[p] == k) return d[u] + d[v] - 2 * d[p]; return inf; } int best_path(int n, int k, int h[][2], int l[]) { for (int i = 0; i < n - 1; ++i) { g[h[i][0]].push_back({h[i][1], l[i]}); g[h[i][1]].push_back({h[i][0], l[i]}); } dfs(0); int res = inf; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) res = min(res, get(i, j, k)); return res < inf ? res : -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...