Submission #980587

#TimeUsernameProblemLanguageResultExecution timeMemory
980587hieptkRace (IOI11_race)C++17
0 / 100
2 ms9052 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 ll inf = 1e18; vector<pair<int, ll>> adj[nm]; int H[nm][2], L[nm]; int Res; bool deleted[nm]; void bfs(int i, int n, int k) { // cout << "bfs " << i << " " << n << " " << k << "\n"; queue<int> q; q.push(i); vector<pair<ll, ll>> d(n, {inf, inf}); d[i] = {0, 0}; while (q.size()) { int i = q.front(); q.pop(); for (auto [j, w]: adj[i]) { if (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 (d[j].second < Res && d[j].first < k) q.push(j); } } } unordered_map<ll, int> best; for (int j = 0; j < n; ++j) { if (d[j].first == inf) continue; if (d[j].first == k) Res = min(Res, (int) d[j].second); else if (best.count(k - d[j].first)) { Res = min(Res, (int) d[j].second + best[k - d[j].first]); } if (best.count(d[j].first)) best[d[j].first] = min(best[d[j].first], (int) d[j].second); else best[d[j].first] = d[j].second; } } void dfs(int i, int p, vector<int> &nchild, vector<int> &maxchild) { nchild[i] = 1; for (auto [j, w]: adj[i]) { if (j == p || deleted[j]) continue; dfs(j, i, nchild, maxchild); nchild[i] += nchild[j]; maxchild[i] = max(maxchild[i], nchild[j]); } } int findCenter(int root, int n) { vector<int> nchild(n), maxchild(n); dfs(root, -1, nchild, maxchild); int s = nchild[root]; if (s == 1) return -1; for (int i = 0; i < n; ++i) { if (nchild[i] > 0) { 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; bfs(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...