제출 #926805

#제출 시각아이디문제언어결과실행 시간메모리
926805Art_ogo경주 (Race) (IOI11_race)C++17
9 / 100
70 ms48540 KiB
#include <bits/stdc++.h> #include "race.h" #define ve vector #define ll long long #define fi first #define se second using namespace std; typedef pair<ll, ll> pll; const int MAXN = 1e6 + 10; ll k; ve<pll> g[MAXN]; map<ll, ll>* st[MAXN]; pll add[MAXN]; ll res; void dfs(int v, int p){ pll mx = {-1, -1}; for(auto& to : g[v]) if(to.fi != p){ dfs(to.fi, v); if(mx.fi == -1 || st[to.fi]->size() > st[mx.fi]->size()) mx = to; } if(mx.fi == -1){ st[v] = new map<ll, ll>(); return; } st[v] = st[mx.fi]; add[v] = add[mx.fi]; add[v].fi += mx.se; add[v].se++; (*st[v])[mx.se - add[v].fi] = min((*st[v])[mx.se - add[v].fi], 1 - add[v].se); for(auto& to : g[v]){ if(to.fi != p && to != mx){ for(auto j : *st[to.fi]){ pll i = j; i.fi += add[to.fi].fi + to.se; i.se += add[to.se].se + 1; ll cur = (k - i.fi) - add[v].fi; if(st[v]->find(cur) != st[v]->end()) res = min(res, (*st[v])[cur] + add[v].se + i.se); } (*st[v])[to.fi - add[v].fi] = min((*st[v])[to.fi - add[v].fi], to.se - add[v].se); } } ll cur = k - add[v].fi; if(st[v]->find(cur) != st[v]->end()) res = min(res, (*st[v])[cur] + add[v].se); st[v]->insert({-add[v].fi, -add[v].se}); //cout << res << endl; } int best_path(int N, int K, int H[][2], int L[]) { k = K; for(int i = 0; i < N; i++){ g[i].clear(); delete(st[i]); add[i] = {0, 0}; res = 1e18; } 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, 0); return res == 1e18 ? -1 : res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...