제출 #185569

#제출 시각아이디문제언어결과실행 시간메모리
185569kdh9949경주 (Race) (IOI11_race)C++17
0 / 100
14 ms9976 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; using pii = pair<int, int>; #define x first #define y second const int N = 200005; int n, k, res = N; vector<pii> e[N]; struct SET{ set<pii> s; pii ofs; SET(): ofs(0, 0) { s.emplace(0, 0); } }; SET *f(int x, int y){ if(x && e[x].size() == 1) return new SET(); vector<SET*> v; SET* mx = NULL; for(pii i : e[x]){ if(i.x == y) continue; v.push_back(f(i.x, x)); v.back()->ofs.x += i.y; v.back()->ofs.y++; if(!mx || mx->s.size() < v.back()->s.size()) mx = v.back(); } for(SET* i : v){ if(i == mx) continue; for(pii j : i->s){ auto it = mx->s.lower_bound(pii(k - (j.x + i->ofs.x), -N)); if(it->x + mx->ofs.x + j.x + i->ofs.x == k) res = min(res, it->y + mx->ofs.y + j.y + i->ofs.y); } for(pii j : i->s){ pii cur(j.x + i->ofs.x - mx->ofs.x, j.y + i->ofs.y - mx->ofs.y); auto it = mx->s.lower_bound(pii(cur.x, -N)); if(it != mx->s.end() && it->x == cur.x){ if(it->y <= cur.y) continue; if(it->y > cur.y) mx->s.erase(it); } mx->s.insert(cur); } } set<pii> t; while(mx->s.rbegin()->x + mx->ofs.x > k) mx->s.erase(*mx->s.rbegin()); mx->s.emplace(-mx->ofs.x, -mx->ofs.y); auto it = mx->s.lower_bound(pii(k - mx->ofs.x, -N)); if(it != mx->s.end() && it->x + mx->ofs.x == k) res = min(res, it->y + mx->ofs.y); return mx; } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for(int i = 0; i < n-1; i++){ e[H[i][0]].emplace_back(H[i][1], L[i]); e[H[i][1]].emplace_back(H[i][0], L[i]); } f(0, -1); return (res == ::N ? -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...