제출 #600512

#제출 시각아이디문제언어결과실행 시간메모리
600512Meloric경주 (Race) (IOI11_race)C++14
21 / 100
3081 ms26272 KiB
#include "race.h" #include <iostream> #include <vector> #include <map> #define int int64_t using namespace std; struct coll { map<int,int> mp = map<int,int>(); int offs = 0; bool operator<(const coll& c2) { return mp.size() < c2.mp.size(); } void insert(int id, int v) { id -= offs; if (mp.find(id) != mp.end()) mp.at(id) = min(v, mp.at(id)); else mp.insert(make_pair(id, v)); } int query(int k) { k -= offs; if (mp.find(k) == mp.end()) return 1e7; return mp.at(k); } static int check(coll& bs, coll& nw, int k, int d) { if (bs < nw) swap(bs, nw); int mn = 1e7; for (auto p : (nw.mp)) { int ck = p.first + nw.offs; if (k < ck) continue; mn = min(mn, bs.query(k - ck) + p.second - 2*d); } return mn; } static coll merge(coll& bs, coll& nw) { if (bs < nw) swap(bs, nw); for (auto p : (nw.mp)) { bs.insert(p.first + nw.offs, p.second); } return bs; } }; struct tree { int n, k; vector<vector<pair<int,int>>> adjlist; int res = 1e7; coll dfs(int curr, int par, int d) { coll rt = coll(); rt.insert(0, d); for (auto p : adjlist[curr]) { if (p.first == par) continue; coll nt = dfs(p.first, curr, d + 1); nt.offs += p.second; res = min(res, coll::check(nt, rt, k, d)); rt = coll::merge(nt, rt); } return rt; } }; signed best_path(signed N, signed K, signed H[][2], signed L[]) { tree t; t.n = N; t.k = K; t.adjlist.resize(N); for (int i = 0; i < N - 1; i++) { t.adjlist[H[i][0]].emplace_back(H[i][1], L[i]); t.adjlist[H[i][1]].emplace_back(H[i][0], L[i]); } t.dfs(0, -1, 0); return (t.res >= N ? -1 : t.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...