Submission #1233977

#TimeUsernameProblemLanguageResultExecution timeMemory
1233977RakhimovAmirClosing Time (IOI23_closing)C++20
43 / 100
105 ms39492 KiB
#include"closing.h" #include<bits/stdc++.h> #include <cstdio> using namespace std; using ll = long long; const ll INF = 1e18; vector<vector<pair<ll, ll>>> v; vector<ll> pref[2]; vector<ll> used[2]; vector<ll> cnt; void dfs(ll x, ll p, ll k) { for (auto [to, w] : v[x]) { if (to == p) continue; pref[k][to] = pref[k][x] + w; dfs(to, x, k); } } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { ll res = 2; v.resize(N); cnt.resize(N); for (ll i = 0; i < 2; i++) { pref[i].resize(N); used[i].resize(N); fill(pref[i].begin(), pref[i].end(), 0); fill(used[i].begin(), used[i].end(), 0); } fill(cnt.begin(), cnt.end(), 0); for (ll i = 0; i < N - 1; i++) { v[U[i]].push_back({V[i], W[i]}); v[V[i]].push_back({U[i], W[i]}); } dfs(X, X, 0); dfs(Y, Y, 1); set<pair<pair<ll, ll>, pair<ll, ll>>> s; used[0][X] = 1; used[1][Y] = 1; cnt[X] = cnt[Y] = 1; // cout << X << " " << Y << "\n"; // for (int i = 0; i < N; i++) { // cout << i << " " << pref[0][i] << " " << pref[1][i] << "\n"; // } for (auto [to, w] : v[X]) { s.insert({{pref[0][to], INF}, {to, 0}}); used[0][to] = 1; if (cnt[to] == 0) { if (!used[0 ^ 1][to]) { s.insert({{pref[0][to], INF}, {to, 0}}); continue; } if (pref[0][to] <= pref[0 ^ 1][to]) { s.insert({{pref[0][to], pref[0 ^ 1][to] - pref[0][to]}, {to, 0}}); } else { s.insert({{pref[0][to], INF}, {to, 0}}); s.erase({{pref[0 ^ 1][to], INF}, {to, 0 ^ 1}}); s.insert({{pref[0 ^ 1][to], pref[0][to] - pref[0 ^ 1][to]}, {to, 0 ^ 1}}); } } else { s.insert({{pref[0][to] - pref[0 ^ 1][to], INF}, {to, 0}}); } } for (auto [to, w] : v[Y]) { used[1][to] = 1; if (cnt[to] == 0) { if (!used[1 ^ 1][to]) { s.insert({{pref[1][to], INF}, {to, 1}}); continue; } if (pref[1][to] <= pref[1 ^ 1][to]) { s.insert({{pref[1][to], pref[1 ^ 1][to] - pref[1][to]}, {to, 1}}); } else { s.insert({{pref[1][to], INF}, {to, 1}}); s.erase({{pref[1 ^ 1][to], INF}, {to, 1 ^ 1}}); s.insert({{pref[1 ^ 1][to], pref[1][to] - pref[1 ^ 1][to]}, {to, 1 ^ 1}}); } } else { s.insert({{pref[1][to] - pref[1 ^ 1][to], INF}, {to, 1}}); } } while (!s.empty()) { auto it = *s.begin(); if (it.first.first > K) break; // cout << "add " << K << " " << it.first << " " << it.second.first << " " << it.second.second << "\n"; res++; s.erase(s.begin()); K -= it.first.first; if (cnt[it.second.first] == 0 && used[it.second.second ^ 1][it.second.first]) { s.erase({{pref[it.second.second ^ 1][it.second.first], INF}, {it.second.first, it.second.second ^ 1}}); s.insert({{pref[it.second.second ^ 1][it.second.first] - it.first.first, INF}, {it.second.first, it.second.second ^ 1}}); // cout << "+ " << pref[it.second.second ^ 1][it.second.first] - it.first << " " << it.second.first << "\n"; } cnt[it.second.first]++; for (auto [to, w] : v[it.second.first]) { if (used[it.second.second][to]) continue; used[it.second.second][to] = 1; if (cnt[to] == 0) { if (!used[it.second.second ^ 1][to]) { s.insert({{pref[it.second.second][to], INF}, {to, it.second.second}}); continue; } if (pref[it.second.second][to] <= pref[it.second.second ^ 1][to]) { s.insert({{pref[it.second.second][to], pref[it.second.second ^ 1][to] - pref[it.second.second][to]}, {to, it.second.second}}); } else { s.insert({{pref[it.second.second][to], INF}, {to, it.second.second}}); s.erase({{pref[it.second.second ^ 1][to], INF}, {to, it.second.second ^ 1}}); s.insert({{pref[it.second.second ^ 1][to], pref[it.second.second][to] - pref[it.second.second ^ 1][to]}, {to, it.second.second ^ 1}}); } } else { s.insert({{pref[it.second.second][to] - pref[it.second.second ^ 1][to], INF}, {to, it.second.second}}); } } } // cout << "_____\n"; for (int i = 0; i < N; i++) { v[i].clear(); } cnt.clear(); for (ll i = 0; i < 2; i++) { used[i].clear(); pref[i].clear(); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...