제출 #668533

#제출 시각아이디문제언어결과실행 시간메모리
668533chanhchuong123경주 (Race) (IOI11_race)C++14
100 / 100
683 ms59928 KiB
#include <bits/stdc++.h> #include <race.h> using namespace std; #define task "C" #define fi first #define se second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } const int N = 2e5 + 3; int n, k; long long h[N]; vector<pair<int, int>> adj[N]; int sz[N], heavy[N], dep[N]; void pre_dfs(int u, int p) { sz[u] = 1; heavy[u] = -1; for (pair<int, int> &x: adj[u]) if (x.fi != p) { int v = x.fi, w = x.se; dep[v] = dep[u] + 1; h[v] = h[u] + w; pre_dfs(v, u); sz[u] += sz[v]; if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v; } } int LCA, ans = N; vector<pair<long long, int>> store; map<pair<long long, int>, int> cnt; void update(int u, int p, int delta) { if (delta == +1) { pair<long long, int> need(k + 2 * h[LCA] - h[u], -1); store.push_back({h[u], dep[u]}); auto it = cnt.lower_bound(need); if (it != cnt.end() && (*it).fi.fi == need.fi) mini(ans, dep[u] + (*it).fi.se - 2 * dep[LCA]); } else { cnt[{h[u], dep[u]}]--; if (!cnt[{h[u], dep[u]}]) cnt.erase({h[u], dep[u]}); } for (pair<int, int> &x: adj[u]) if (x.fi != p) update(x.fi, u, delta); } void dfs(int u, int p) { for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) { dfs(x.fi, u); update(x.fi, u, -1); } if (heavy[u] != -1) { dfs(heavy[u], u); LCA = u; for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) { update(x.fi, u, +1); while (store.size()) { cnt[store.back()]++; store.pop_back(); } } } auto it = cnt.lower_bound({h[u] + k, -1}); if (it != cnt.end() && (*it).fi.fi == h[u] + k) mini(ans, (*it).fi.se - dep[u]); cnt[{h[u], 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 u = H[i][0], v = H[i][1], w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } pre_dfs(0, -1); dfs(0, -1); return (ans == N ? -1 : ans); } /* int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> k; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } pre_dfs(0, -1); dfs(0, -1); cout << (ans == N ? -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...