Submission #24194

#TimeUsernameProblemLanguageResultExecution timeMemory
24194NirjhorRace (IOI11_race)C++14
100 / 100
887 ms76284 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; typedef long long ll; typedef pair <int, ll> edge; #define x first #define y second const int N = 200010; const int INF = 1e9 + 10; vector <edge> g[N]; int n, k, ans = INF; void dfs (int u, int from, map <ll, int> &f, ll &key_f, int &val_f) { f[0] = 0; key_f = val_f = 0; for (edge e : g[u]) { int v = e.x; ll w = e.y; if (v == from) continue; map <ll, int> t; ll key_t; int val_t; dfs(v, u, t, key_t, val_t); key_t += w, ++val_t; if (t.size() > f.size()) { f.swap(t); swap(key_f, key_t); swap(val_f, val_t); } for (auto it : t) { ll more = k - it.x - key_t - key_f; if (f.find(more) != f.end()) { ans = min(ans, it.y + f[more] + val_t + val_f); } } key_t -= key_f, val_t -= val_f; for (auto it : t) { if (f.find(it.x + key_t) == f.end()) f[it.x + key_t] = INF; f[it.x + key_t] = min(f[it.x + key_t], it.y + val_t); } } // cout << u << " ----> \n"; // for (auto it : f) { // cout << it.x << " " << it.y << endl; // } } int best_path (int N, int K, int H[][2], int L[]) { n = N, k = K; for (int i = 0; i < n - 1; ++i) { g[H[i][0]].emplace_back(H[i][1], L[i]); g[H[i][1]].emplace_back(H[i][0], L[i]); } map <ll, int> f; ll key; int val; dfs(0, 0, f, key, val); if (ans >= INF / 2) ans = -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...