Submission #999645

#TimeUsernameProblemLanguageResultExecution timeMemory
999645biankClosing Time (IOI23_closing)C++17
100 / 100
127 ms33212 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) int(x.size()) #define all(x) begin(x), end(x) using ll = long long; using ii = pair<int, int>; const ll INF = 1e18; const int MAX_N = 2e5 + 9; vector<ii> adj[MAX_N]; int n; void dfs(int u, vector<ll> &dist, int p = -1, ll d = 0) { dist[u] = d; for (auto [v, w] : adj[u]) { if (v != p) dfs(v, dist, u, d + w); } } int non_overlaping(ll K, vector<ll> v) { sort(all(v)); int ans = 0; for (int i = 0; i < n; i++) { if (v[i] <= K) { K -= v[i]; ans++; } } return ans; } int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) { n = N; for (int i = 0; i < n; i++) adj[i].clear(); for (int i = 0; i < n - 1; i++) { adj[U[i]].emplace_back(V[i], W[i]); adj[V[i]].emplace_back(U[i], W[i]); } vector<ll> dist1(n), dist2(n); dfs(X, dist1), dfs(Y, dist2); vector<bool> path(n, false); path[Y] = true; int u = Y; while (u != X) { for (auto [v, w] : adj[u]) { if (dist1[v] + w == dist1[u]) { u = v; break; } } path[u] = true; } for (int i = 0; i < n; i++) { if (dist1[i] > dist2[i]) swap(dist1[i], dist2[i]); } vector<ll> vec1; vector<pair<ll, ll>> vec2; ll remain = K; int curr = 0; for (int i = 0; i < n; i++) { ll val1 = dist1[i]; ll val2 = dist2[i] - dist1[i]; if (path[i]) { remain -= val1, curr++; vec1.push_back(val2); } else if (val1 <= val2) { vec1.push_back(val1); vec1.push_back(val2); } else { vec2.emplace_back(val1, val2); } } sort(all(vec1)); sort(all(vec2), [](const pair<ll, ll> &a, const pair<ll, ll> &b) { return a.first + a.second < b.first + b.second; }); int S = sz(vec1); vector<ll> prefSum(S + 1); prefSum[0] = 0LL; for (int i = 0; i < S; i++) { prefSum[i + 1] = vec1[i]; prefSum[i + 1] += prefSum[i]; } int M = sz(vec2); vector<ll> prefMaxi(M + 1); prefMaxi[0] = -INF; for (int i = 0; i < M; i++) { prefMaxi[i + 1] = vec2[i].second; prefMaxi[i + 1] = max(prefMaxi[i + 1], prefMaxi[i]); } vector<ll> suffMini(M + 2); suffMini[M + 1] = suffMini[M] = INF; for (int i = M - 1; i >= 0; i--) { suffMini[i] = vec2[i].first; suffMini[i] = min(suffMini[i], suffMini[i + 1]); } auto calc = [&](ll r) { if (remain < 0) return int(-1e9); auto it = upper_bound(all(prefSum), r); return int(it - prefSum.begin()) - 1; }; int ans = non_overlaping(K, dist1); for (int i = 0; i <= M; i++) { if (i > 0) { remain -= vec2[i - 1].first + vec2[i - 1].second; curr += 2; } ans = max({ans, curr + calc(remain), curr + 1 + calc(remain - suffMini[i]), curr - 1 + calc(remain + prefMaxi[i])}); } return 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...
#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...