제출 #539380

#제출 시각아이디문제언어결과실행 시간메모리
539380noedit경주 (Race) (IOI11_race)C++17
0 / 100
67 ms105140 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; typedef long long ll; const int MAXN = 2e5; const int MAXK = 1e6 + 1; vector<pair<int, int> > g[MAXN]; vector<int>* vec[MAXN]; int sz[MAXN], big[MAXN]; map<int, int> cnt[MAXK]; int dep[MAXN]; ll d[MAXN]; void sizes(int v, int p, int depth = 0, ll dist = 0) { dep[v] = depth; d[v] = dist; sz[v] = 1; int b = -1, mx = 0; for (auto& [u, w]: g[v]) { if (u != p) { sizes(u, v, depth + 1, dist + w); sz[v] += sz[u]; if (sz[u] > mx) { mx = sz[u]; b = u; } } } big[v] = b; } int ans = 1e9, k, n; void dfs(int v, int p, bool keep = 0) { for (auto& [u, w] : g[v]) { if (u != p && u != big[v]) { dfs(u, v, 0); } } if (big[v] != -1) { dfs(big[v], v, 1); vec[v] = vec[big[v]]; } else { vec[v] = new vector<int>(); } vec[v]->push_back(v); ll y = k + d[v]; if (cnt[y].size() > 0 && cnt[y].begin()->first - dep[v] < ans) { ans = cnt[y].begin()->first - dep[v]; } if (d[v] < MAXK) { cnt[d[v]][dep[v]]++; } for (auto& [u, w] : g[v]) { if (u != p && u != big[v]) { for (auto& w : *vec[u]) { ll x = k * 1ll + 2 * 1ll * d[v] - d[w]; if (x >= 0 && x < MAXK && cnt[x].size() > 0) { ll cur = cnt[x].begin()->first + dep[w]; if (cur - 2 * 1ll * dep[v] < ans) { ans = cur - 2 * dep[v]; } } vec[v]->push_back(w); } for (auto& w : *vec[u]) if (d[w] < MAXK) cnt[d[w]][dep[w]]++; } } if (!keep) { for (auto& u : *vec[v]) { if (d[u] < MAXK){ cnt[d[u]][dep[u]]--; if (!cnt[d[u]].count(dep[u])) cnt[d[u]].erase(dep[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 x = H[i][0], y = H[i][1], z = L[i]; g[x].push_back({y, z}); g[y].push_back({x, z}); } sizes(0, 0); dfs(0, 0); return (ans == 1e9 ? -1 :ans); } /* 4 3 0 1 1 1 2 2 1 3 4 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...