Submission #998186

#TimeUsernameProblemLanguageResultExecution timeMemory
998186The_SamuraiRace (IOI11_race)C++17
21 / 100
3071 ms58356 KiB
#include "bits/stdc++.h" #include "race.h" using namespace std; using ll = long long; const int inf = 1e9, N = 2e5 + 5; int ans = inf, k, z = 0; vector<vector<pair<int, int>>> g(N); vector<int> par(N, -1), heavy(N), height2(N); vector<ll> height(N); vector<set<pair<ll, int>>> st; /* */ int dfs(int u) { int size = 1, max_child_size = 0; for (auto [v, w]: g[u]) { if (par[u] == v) continue; height[v] = height[u] + w; height2[v] = height2[u] + 1; par[v] = u; int child_size = dfs(v); if (child_size > max_child_size) { heavy[u] = heavy[v]; max_child_size = child_size; } size += child_size; } if (size == 1) { heavy[u] = z++; st.emplace_back(); } return size; } void dfs2(int u) { for (auto [v, w]: g[u]) { if (par[u] == v) continue; dfs2(v); } for (auto [v, w]: g[u]) { if (par[u] == v or heavy[u] == heavy[v]) continue; for (auto it: st[heavy[v]]) { ll need = k - (it.first - height[u]) + height[u]; auto it2 = st[heavy[u]].lower_bound(make_pair(need, 0)); if (it2 != st[heavy[u]].end() and it2->first == need) { ans = min(ans, it.second + it2->second - 2 * height2[u]); } } for (auto it: st[heavy[v]]) { st[heavy[u]].insert(it); } st[heavy[v]].clear(); } ll need = k + height[u]; auto it = st[heavy[u]].lower_bound(make_pair(need, 0)); if (it != st[heavy[u]].end() and it->first == need) { ans = min(ans, it->second - height2[u]); } st[heavy[u]].emplace(height[u], height2[u]); vector<pair<ll, int>> del; pair<ll, int> last = {-1, -1}; for (auto it: st[heavy[u]]) { if (it.first == last.first) { del.emplace_back(it); } last = it; } for (auto it: del) st[heavy[u]].erase(it); } int best_path(int n, int K, int H[][2], int L[]) { 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]); } // change it dfs(0); dfs2(0); return ans == inf ? -1 : 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...