Submission #980647

#TimeUsernameProblemLanguageResultExecution timeMemory
980647hieptkRace (IOI11_race)C++17
21 / 100
3018 ms20508 KiB
#include <iostream> #include <vector> #include <cmath> #include <numeric> #include <algorithm> #include <set> #include <unordered_set> #include <cstring> #include <unordered_map> #include <iomanip> #include <queue> #include <map> #include <sstream> #include <stack> #include <bitset> using ll = long long; using ld = long double; using namespace std; const int nm = 200002; const int inf = 1e9; vector<pair<int, int>> adj[nm]; int H[nm][2], L[nm]; int Res; bool deleted[nm]; unordered_map<int, int> bfs(int i, int p, int n, int k) { queue<int> q; q.push(i); vector<pair<int, int>> d(n, {inf, inf}); d[i] = {0, 0}; unordered_map<int, int> res; res[0] = 0; while (q.size()) { int i = q.front(); q.pop(); for (auto [j, w]: adj[i]) { if (j == p || deleted[j]) continue; if (d[j].second > d[i].second + 1) { d[j].first = d[i].first + w; d[j].second = d[i].second + 1; if (!res.count(d[j].first)) res[d[j].first] = d[j].second; else res[d[j].first] = min(res[d[j].first], d[j].second); if (d[j].second < Res && d[j].first < k) q.push(j); } } } return res; } void check(int root, int n, int k) { unordered_map<int, int> res; for (auto [j, w]: adj[root]) { if (deleted[j]) continue; auto resj = bfs(j, root, n, k); for (auto [cost, len]: resj) { if (cost + w > k) continue; if (cost + w == k) { Res = min(Res, len + 1); } else if (res.count(k - cost - w)) { Res = min(Res, res[k - cost - w] + len + 1); } } for (auto [cost, len]: resj) { if (cost + w > k) continue; if (res.count(cost + w)) { res[cost + w] = min(res[cost + w], len + 1); } else { res[cost + w] = len + 1; } } } } void dfs(int i, int p, vector<int> &nchild, vector<int> &maxchild, unordered_set<int> &visited) { nchild[i] = 1; visited.insert(i); for (auto [j, w]: adj[i]) { if (j == p || deleted[j]) continue; dfs(j, i, nchild, maxchild, visited); nchild[i] += nchild[j]; maxchild[i] = max(maxchild[i], nchild[j]); } } int findCenter(int root, int n) { vector<int> nchild(n), maxchild(n); unordered_set<int> visited; dfs(root, -1, nchild, maxchild, visited); int s = nchild[root]; if (s == 1) return -1; for (int i: visited) { int maxsplit = max(maxchild[i], s - nchild[i]); if (maxsplit <= s / 2) return i; } return -1; } void calc(int root, int n, int k) { int u = findCenter(root, n); // cout << "root " << root << " center " << u << "\n"; if (u == -1) return; check(u, n, k); // cout << "root " << root << " center " << u << " " << Res << "\n"; deleted[u] = 1; for (auto [j, w]: adj[u]) { if (!deleted[j]) calc(j, n, k); } } int best_path(int n, int k, int H[][2], int L[]) { for (int i = 0; i < n - 1; ++i) { adj[H[i][0]].emplace_back(H[i][1], L[i]); adj[H[i][1]].emplace_back(H[i][0], L[i]); } memset(deleted, 0, sizeof(deleted)); Res = n + 1; calc(0, n, k); return Res < n ? Res : -1; } // int main() { // #ifdef LOCAL // freopen("input.txt", "r", stdin); // #endif // ios::sync_with_stdio(0); // cin.tie(0); // int n, k; // cin >> n >> k; // for (int i = 0; i < n - 1; ++i) cin >> H[i][0] >> H[i][1] >> L[i]; // cout << best_path(n, k, H, L) << "\n"; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...