Submission #499795

#TimeUsernameProblemLanguageResultExecution timeMemory
499795zxcvbnmRace (IOI11_race)C++14
0 / 100
4 ms4940 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; constexpr int nax = 2e5 + 5; vector<pair<int, int>> adj[nax]; int k; struct Centroid { vector<int> sz; vector<bool> vis; int ans = INT_MAX; void init(int n) { sz.resize(n); vis.assign(n, false); } int find_size(int v, int p=-1) { if (vis[v]) { return 0; } sz[v] = 1; for(auto u : adj[v]) { if (u.first == p) continue; sz[v] += find_size(u.first, v); } return sz[v]; } int find_centroid(int v, int p, int n) { for(auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; if (sz[u.first] > n/2) { return find_centroid(u.first, v, n); } } return v; } map<int, int> mp; void dfs(int v, int p, int depth, int cost, bool filling) { if (cost > k) return; // cerr << "v: " << depth << " " << cost << "\n"; if (cost == k) { ans = min(ans, depth); return; } if (filling) { if (mp.find(cost) == mp.end() || mp[cost] > depth) { mp[cost] = depth; } } else { if (mp.find(k-cost) != mp.end()) { ans = min(ans, depth + mp[k-cost]); // cerr << "in: " << depth + mp[k-cost] << "\n"; } } for(auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; // dfs(u.first, v, depth+1, cost+u.second, filling); } } void sol(int v) { mp.clear(); for(auto u : adj[v]) { if (vis[u.first]) continue; // cout << v << "->" << u.first << " cost " << u.second << "\n"; dfs(u.first, v, 1, u.second, false); dfs(u.first, v, 1, u.second, true); } } void init_centroid(int v=0, int p=-1) { find_size(v); int c = find_centroid(v, p, sz[v]); vis[c] = true; sol(c); // cout << c << " " << ans << "\n"; for(auto u : adj[c]) { if (!vis[u.first]) { init_centroid(u.first, c); } } } }; int best_path(int N, int K, int H[][2], int L[]) { k = K; for(int i = 0; i < N-1; i++) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } Centroid ct; ct.init(N+6); ct.init_centroid(); return ct.ans == INT_MAX ? -1 : ct.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...