제출 #704750

#제출 시각아이디문제언어결과실행 시간메모리
704750thimote75경주 (Race) (IOI11_race)C++14
100 / 100
1167 ms64672 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define num long long #define di pair<int, num> #define sdi set<di> #define graph vector<sdi> #define idata vector<int> #define INF 1e18 graph roads; int nbNodes, pathLength; struct MMap { map<num, num> m; bool has (num depth) { return m.find(depth) != m.end(); } num get (num depth) { return (*(m.find(depth))).second; } void set (num depth, num value) { if (has(depth)) { value = min(value, get(depth)); m.erase(depth); } m.insert({ depth, value }); } void clear () { m.clear(); } void show () { for (auto u : m) printf("%lld:%lld ", u.first, u.second); cout << endl; } }; struct CDecompose { num answer = 1e18; idata subtree; MMap min_map; void init () { subtree.resize(nbNodes); build (0, -1); } void build (int node, int parent) { int compSize = w_dfs(node, parent); int centroid = c_dfs(node, parent, compSize >> 1); min_map.set(0, 0); for (di next : roads[centroid]) { comp(next.first, centroid, next.second, 1); fill(next.first, centroid, next.second, 1); } min_map.clear(); while (roads[centroid].size() != 0) { di err = *roads[centroid].begin(); roads[centroid ].erase(err); roads[err.first].erase({ centroid, err.second }); build (err.first, -1); } } int w_dfs (int node, int parent) { subtree[node] = 1; for (di next : roads[node]) { if (next.first == parent) continue ; subtree[node] += w_dfs(next.first, node); } return subtree[node]; } int c_dfs (int node, int parent, int desired) { for (di next : roads[node]) if (next.first != parent && desired <= subtree[next.first]) return c_dfs(next.first, node, desired); return node; } void comp (int node, int parent, num length, int depth) { if (length > pathLength) return ; if (depth > answer) return ; if (min_map.has(pathLength - length)) { answer = min( answer, min_map.get(pathLength - length) + depth ); } for (di next : roads[node]) { if (next.first == parent) continue ; comp(next.first, node, length + next.second, depth + 1); } } void fill (int node, int parent, num length, int depth) { if (length > pathLength) return ; if (depth > answer) return ; min_map.set(length, depth); for (di next : roads[node]) { if (next.first == parent) continue ; fill(next.first, node, length + next.second, depth + 1); } } }; int best_path(int N, int K, int H[][2], int L[]) { nbNodes = N; pathLength = K; roads.resize(nbNodes); for (int idRoad = 0; idRoad + 1 < nbNodes; idRoad ++) { int a, b; num l; a = H[idRoad][0]; b = H[idRoad][1]; l = L[idRoad]; roads[a].insert({ b, l }); roads[b].insert({ a, l }); } CDecompose dec; dec.init(); return dec.answer == INF ? -1 : dec.answer; } /*int main () { int N, K; cin >> N >> K; int H[N][2]; int L[N]; for (int i = 0; i + 1 < N; i++) cin >> H[i][0] >> H[i][1] >> L[i]; printf("%d", best_path(N, K, H, L)); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...