제출 #1083479

#제출 시각아이디문제언어결과실행 시간메모리
1083479Namviet2704경주 (Race) (IOI11_race)C++17
9 / 100
455 ms14336 KiB
#include <bits/stdc++.h> //#include "race.h" #define ll long long #define fi first #define se second #define pii pair<int, int> using namespace std; const int N = 2e5 + 5; int n, k, ans = 1e9; vector<pii> vt[N]; int in[N], out[N], pos[N], sz[N], kq[N]; pair<ll, int> h[N]; int cnt = 0; void dfs(int u, int p) { in[u] = ++cnt; pos[cnt] = u; sz[u] = 1; for(auto v : vt[u]) { if(v.fi == p) continue; h[v.fi].fi = h[u].fi + v.se; h[v.fi].se = h[u].se + 1; dfs(v.fi, u); sz[u] += sz[v.fi]; } out[u] = cnt; } map<ll, pii> mp; void add(int u) { for(int i = in[u]; i <= out[u]; i++) { if(mp[h[pos[i]].fi].fi == 0) mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]}; else mp[h[pos[i]].fi] = min(mp[h[pos[i]].fi], {h[pos[i]].se, pos[i]}); } } void del(int u) { for(int i = in[u]; i <= out[u]; i++) mp[h[pos[i]].fi] = {0, 0}; } void solve(int u, int p) { pair<int, int> big = {0, -1}; for(auto v : vt[u]) if(v.fi != p) big = max(big, {sz[v.fi], v.fi}); for(auto v : vt[u]) { if(v.fi == big.se || v.fi == p) continue; solve(v.fi, u); del(v.fi); } if(big.se != -1) solve(big.se, u); for(auto v : vt[u]) if(v.fi != big.se) add(v.fi); mp[h[u].fi] = {h[u].se, u}; for(int i = in[u]; i <= out[u]; i++) { if(big.se != -1 && in[big.se] <= i && i <= out[big.se]) continue; int v = pos[i]; ll tmp = h[u].fi + k - (h[v].fi - h[u].fi); // cout << u << " " << v << " " << tmp << " " << mp[tmp].fi << '\n'; if(mp[tmp].fi == 0) continue; int haha = mp[tmp].se; if(out[haha] < in[v] || out[v] < in[haha] || v == u) ans = min(ans, h[haha].se - h[u].se + h[v].se - h[u].se); } return; } int best_path(int m, int g, int h[][2], int l[]) { n = m; k = g; for(int i = 0; i < n - 1; i++) { vt[h[i][0]].push_back({h[i][1], l[i]}); vt[h[i][1]].push_back({h[i][0], l[i]}); } dfs(0, -1); solve(0, -1); if(ans == (int) 1e9) return -1; return ans; } //int main() //{ //// freopen(task".inp", "r", stdin); //// freopen(task".out", "w", stdout); // ios_base::sync_with_stdio(false); // cin.tie(NULL), cout.tie(NULL); // cin >> n >> k; // for(int i = 1; i < n; i++) // { // int x, y, w; // cin >> x >> y >> w; // vt[x].push_back({y, w}); // vt[y].push_back({x, w}); // } // dfs(0, -1); // cout << best_path(); // return 0; //} /* 4 3 0 1 1 1 2 2 1 3 4 11 12 0 1 3 0 2 4 2 3 5 3 4 4 4 5 6 0 6 3 6 7 2 6 8 5 8 9 6 8 10 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...