Submission #840919

#TimeUsernameProblemLanguageResultExecution timeMemory
840919nicksmsClosing Time (IOI23_closing)C++17
43 / 100
207 ms54184 KiB
#include "closing.h" /** * Author: Nicholas Winschel * Created: 08.31.2023 14:51:13 **/ #include <bits/stdc++.h> using namespace std; using ll=long long; using db=long double; template<class T> using V=vector<T>; using vi = V<int>; using vl = V<ll>; using pi = pair<int,int>; #define f first #define s second #define sz(x) (int)((x).size()) #include <vector> int max_score(int N, int X, int Y, long long K, std::vector<int> u, std::vector<int> v, std::vector<int> W) { // assume cannot/optimal not to reach common vertex // overestimates cost in the case that it is possible and optimal // swap(u,v); ll oK = K; V<vi> adj(N); for (int i = 0; i < N-1; i++) { adj[u[i]].push_back(i); adj[v[i]].push_back(i); } struct op { ll c; int v, p; op () {} op(ll c, int v, int p) : c(c), v(v), p(p) {} bool operator<(const op b) const { return c < b.c; } bool operator>(const op b) const { return c > b.c; } }; priority_queue<op, V<op>, greater<op>> pq; pq.emplace(0,X,-1); pq.emplace(0,Y,-1); int ans1 = 0; while (sz(pq)) { op e = pq.top(); pq.pop(); if (e.c > K) continue; K -= e.c; ans1++; for (int i : adj[e.v]) { int x = u[i] == e.v ? v[i] : u[i]; if (x == e.p) continue; pq.emplace(e.c+W[i],x,e.v); } } K = oK; vl dist1(N), dist2(N); auto dfs = [&](int vv, int p, ll d, vl &a, auto &&dfs) -> void { a[vv] = d; for (int i : adj[vv]) { int x = u[i] == vv ? v[i] : u[i]; if (x == p) continue; dfs(x, vv, d+W[i], a, dfs); } }; dfs(X, -1, 0, dist1, dfs); dfs(Y, -1, 0, dist2, dfs); // for (auto x : dist1) cerr << x << " "; //cerr << "\n"; // for (auto x : dist2) cerr << x << " "; //cerr << "\n"; ll btw = dist2[X]; V<bool> done(2*N); using sins = tuple<ll, int, int>; // cost, op, prev using dins = tuple<ll, int, int, int>; // cost, op1, op2, prev priority_queue<sins, V<sins>, greater<sins>> q1; priority_queue<dins, V<dins>, greater<dins>> q2; int ans = 0; auto perform = [&](int op, int prev) { //cerr << "dbg: " << K << " " << op << " " << prev << "\n"; int vert = op >= N ? op - N : op; assert(!done[op]); ans++; if ((op < N) != (dist1[vert] <= dist2[vert])) { // NO KIDS done[op] = true; } else { done[op] = true; ll cu = abs(dist2[vert]-dist1[vert]); q1.emplace(cu, N-(op-vert) + vert, vert); // opposite bool b = (dist2[vert] >= dist1[vert]); for (int i : adj[vert]) { int x = u[i] == vert ? v[i] : u[i]; if (x == prev) continue; if ((dist2[x] >= dist1[x]) != b) continue; q1.emplace(min(dist1[x], dist2[x]), x + op - vert, vert); // child q2.emplace(max(dist1[x], dist2[x]), x, x+N, vert); // both child for (int j : adj[x]) { // this is only OK because we are in a tree... int y = u[j] == x ? v[j] : u[j]; if (y == vert) continue; if ((dist2[y] >= dist1[y]) != b) continue; q2.emplace(min(dist1[x], dist2[x]) + min(dist1[y], dist2[y]), x + op - vert, y + op - vert, vert); } } } }; for (int i = 0; i < N; i++) { if (dist1[i] + dist2[i] == btw) { if (dist1[i] <= dist2[i]) { K -= dist1[i]; perform(i, -1); } else { K -= dist2[i]; perform(i + N, -1); } } } if (K < 0) return ans1; //cerr << "???\n"; //cerr << sz(q1) << " " << sz(q2) << "\n"; while (sz(q1) || sz(q2)) { while (q2.size()) { auto [cu, fi, se, pre] = q2.top(); if (done[fi] || done[se] || cu > K) { //cerr << "popping q2: " << cu << " " << fi << " " << se << " " << pre << "\n"; q2.pop(); // //cerr << "Popped q2!\n"; } else break; } while (q1.size()) { auto [cu, op, pre] = q1.top(); if (done[op] || cu > K) { //cerr << "popping q1: " << cu << " " << op << " " << pre << "\n"; q1.pop(); // //cerr << "Popped q1!\n"; } else break; } //cerr << "body\n"; if (q1.size() && !q2.size()) { //cerr << "path1\n"; auto [cu, op, pre] = q1.top(); q1.pop(); K -= cu; perform(op, pre); } else if (q2.size()) { //cerr << "path2\n"; assert(q1.size()); auto o1 = q1.top(); q1.pop(); while (q1.size()) { auto [cu, op, pre] = q1.top(); if (done[op] || cu > K) { q1.pop(); } else break; } auto ob = q2.top(); if (sz(q1)) { // not given auto [cu1, op1, pre1] = o1; auto o2 = q1.top(); auto [cu2, op2, pre2] = o2; // q1.pop(); auto [cub, fi, se, preb] = ob; if (cub <= cu1 + cu2) { q2.pop(); K -= cub; perform(fi, preb); perform(se, fi >= N ? fi - N : fi); q1.push(o1); // q1.push(o2); } else { K -= cu1; perform(op1, pre1); // q1.push(o2); // q2.push(ob); } } else { q1.push(o1); auto [cub, fi, se, preb] = ob; q2.pop(); K -= cub; perform(fi, preb); perform(se, fi >= N ? fi - N : fi); } } } return max(ans, ans1); }
#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...