Submission #999544

#TimeUsernameProblemLanguageResultExecution timeMemory
999544WaelClosing Time (IOI23_closing)C++17
100 / 100
362 ms80072 KiB
#include "closing.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; using i64 = long long; int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W) { vector<vector<pair<int, int>>> adj(n); for (int i = 0; i < n - 1; ++i) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } vector<vector<i64>> dis(n, vector<i64>(2, 0)); vector<vector<int>> next(n, vector<int>(2, -1)); function<void(int, int, int)> dfs = [&](int u, int p, int t) { for (auto [v, w] : adj[u]) { if (v == p) continue; dis[v][t] = dis[u][t] + w; next[v][!t] = u; dfs(v, u, t); } }; dfs(x, -1, 0); dfs(y, -1, 1); vector<int> path, onPath(n, 0); int z = x; while (true) { path.push_back(z); onPath[z] = 1; if (z == y) { break; } z = next[z][0]; } vector<i64> one(n), two(n), upgCost(n); for (int u = 0; u < n; ++u) { one[u] = min(dis[u][0], dis[u][1]); two[u] = max(dis[u][0], dis[u][1]); upgCost[u] = two[u] - one[u]; } vector<int> used(n, 0); auto work = [&](bool mark, i64 k) { int ret = 0; vector<bool> vis(n, 0); priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq; pq.push({0, x}); pq.push({0, y}); while (pq.size()) { auto [cost, u] = pq.top(); pq.pop(); if (cost > k) { break; } if (vis[u]) { continue; } vis[u] = 1; k -= cost; ++ret; for (auto [v, w] : adj[u]) { pq.push({one[v], v}); } } return ret; }; int ans1 = work(0, k); int ans2 = 0; set<pair<i64, int>> upgrade; set<pair<i64, int>> take; set<pair<i64, int>> average; for (auto u : path) { k -= one[u]; ++ans2; upgrade.insert({upgCost[u], u}); } if (k < 0) { return ans1; } for (int u = 0; u < n; ++u) { if (onPath[u]) continue; take.insert({one[u], u}); average.insert({two[u], u}); } int last = -1; while (ans2 < 2 * n) { i64 mn = 1e18, type = 0; if (take.size()) { mn = take.begin() -> first; type = 1; } if (upgrade.size()) { if (upgrade.begin() -> first < mn) { type = 2; } mn = min(mn, upgrade.begin() -> first); } if (average.size()) { if ((average.begin() -> first + 1) / 2 <= mn && average.begin() -> first <= k) { type = 3; } } if (mn > k && type != 3) { break; } if (type == 1) { auto [cost, u] = *take.begin(); k -= cost; average.erase({two[u], u}); take.erase(take.begin()); upgrade.insert({upgCost[u], u}); ++ans2; last = cost; } else if (type == 2) { auto [cost, u] = *upgrade.begin(); k -= cost; upgrade.erase(upgrade.begin()); ++ans2; last = cost; } else if (type == 3) { auto [cost, u] = *average.begin(); k -= cost; take.erase({one[u], u}); average.erase(average.begin()); ans2 += 2; } } if (average.size() && k + last >= average.begin() -> first) { ++ans2; } return max(ans1, ans2); }
#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...