Submission #1241693

#TimeUsernameProblemLanguageResultExecution timeMemory
1241693banganClosing Time (IOI23_closing)C++20
0 / 100
1098 ms42104 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define ALL(a) a.begin(), a.end() #define ll long long #define MP make_pair #define pii pair<int, int> const ll INF = 1ll << 50; // const int MXN = 1<<20; int none(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<vector<pii>> adj(N); for (int i=0; i < N-1; i++) { adj[V[i]].eb(U[i], W[i]); adj[U[i]].eb(V[i], W[i]); } vector<bool> done(N); vector<ll> d(N, INF); d[X] = d[Y] = 0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(0, X); pq.emplace(0, Y); int ans = 0; while (!pq.empty()) { auto [_, v] = pq.top(); pq.pop(); if (done[v]) continue; done[v] = true; if (d[v] <= K) { ans++; K -= d[v]; } for (auto [u, w] : adj[v]) if (d[v]+w < d[u]) { d[u] = d[v]+w; pq.push(MP(d[u], u)); } } return ans; } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<vector<pii>> adj(N); for (int i=0; i < N-1; i++) { adj[V[i]].eb(U[i], W[i]); adj[U[i]].eb(V[i], W[i]); } vector<array<ll, 2>> f(N); auto dfs = [&](auto self, int v, int p, int c) -> void { for (auto [u, w] : adj[v]) if (u!=p) { f[u][c] = f[v][c] + w; self(self, u, v, c); } }; dfs(dfs, X, X, 0); dfs(dfs, Y, Y, 1); vector<int> save_by_x(N), save_by_y(N); iota(ALL(save_by_x), 0); iota(ALL(save_by_y), 0); sort(ALL(save_by_x), [&](int v, int u) { return f[v][0]>f[u][0]; }); sort(ALL(save_by_y), [&](int v, int u) { return f[v][1]>f[u][1]; }); vector<int> save_c(N, -1); { vector<int> stk; auto DFS = [&](auto self, int v, int p) -> void { stk.pb(v); if (v == Y) for (int it : stk) save_c[it] = min(f[it][0], f[it][1]); for (auto [u, w] : adj[v]) if (u!=p) { self(self, u, v); } stk.pop_back(); }; DFS(DFS, X, X); } int ans = none(N, X, Y, K, U, V, W); auto check = [&](int m, int l) { vector<int> all; vector<int> c = save_c; auto add = [&](auto self, int v, int fa) -> void { if (c[v] != -1) all.pb(v); for (auto [u, w] : adj[v]) if (c[u] != -1 && u!=fa) self(self, u, v); }; vector<int> P; for (int v=0; v<N; v++) if (c[v] != -1) P.pb(v); sort(ALL(P), [&](int v, int u) { return max(f[v][0],f[v][1]) > max(f[u][0],f[u][1]); }); if (P.size()<l) return -1; ll k = K; for (int it : c) if (it != -1) k -= it; for (int _=0; _<l; _++) { int v = P.back(); P.pop_back(); if (c[v] != -1) k += c[v]; c[v] = max(f[v][0], f[v][1]); k -= c[v]; add(add, v, v); } sort(ALL(all), [&](int v, int u) { return max(f[v][0],f[v][1]) > max(f[u][0],f[u][1]); }); if (all.size()<m) return -1; for (int _=0; _<m; _++) { int v = all.back(); all.pop_back(); if (c[v] != -1) k += c[v]; c[v] = max(f[v][0], f[v][1]); k -= c[v]; } if (k<0) return -1; int res = 0; vector<int> by_x = save_by_x; vector<int> by_y = save_by_y; while (!by_x.empty() || !by_y.empty()) { bool flg = false; if (!by_x.empty() && !by_y.empty()) { int v = by_x.back(); int u = by_y.back(); if (f[v][0]<f[u][1]) flg = true; } if (by_y.empty() || flg) { int v = by_x.back(); by_x.pop_back(); if (f[v][1]<=f[v][0] && c[v] < f[v][0]) continue; if (c[v] != -1 || f[v][0]<=k) { res++; if (c[v] == -1) k -= f[v][0]; } } else { int v = by_y.back(); by_y.pop_back(); if (f[v][0]<=f[v][1] && c[v] < f[v][1]) continue; if (c[v] != -1 || f[v][1]<=k) { res++; if (c[v] == -1) k -= f[v][1]; } } } return res; }; // for (int k=MXN; 1<=k; k>>=1) if (m+k <= N && check(m+k) != -1) m += k; // return max(ans, check(m)); for (int m=0; m <= N; m++) for (int l=1; l <= N; l++) ans = max(ans, check(m, l)); 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...