Submission #1212633

#TimeUsernameProblemLanguageResultExecution timeMemory
1212633trimkusClosing Time (IOI23_closing)C++20
9 / 100
51 ms20288 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; using ll = long long; 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<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<int> line; vector<int> idx(N); vector<vector<int>> W(2, vector<int>(N)); { int p = -1; int v; for (int i = 0; i < N; ++i) { if ((int)adj[i].size() == 1) { v = i; break; } } line.push_back(v); while (true) { bool ok = false; for (auto& [u, w] : adj[line.back()]) { if (u == p) continue; p = line.back(); line.push_back(u); ok = true; break; } if (!ok) break; } assert((int)line.size() == N); for (int i = 0; i < N; ++i) { idx[line[i]] = i; } int id = idx[X]; while (id > 0) { int now = line[id]; int to = line[id - 1]; for (auto& [u, w] : adj[now]) { if (u == to) { W[0][id - 1] = w; } } id--; } id = idx[X]; while (id + 1 < N) { int now = line[id]; int to = line[id + 1]; for (auto& [u, w] : adj[now]) { if (u == to) { W[0][id + 1] = w; } } id++; } id = idx[Y]; while (id > 0) { int now = line[id]; int to = line[id - 1]; for (auto& [u, w] : adj[now]) { if (u == to) { W[1][id - 1] = w; } } id--; } id = idx[Y]; while (id + 1 < N) { int now = line[id]; int to = line[id + 1]; for (auto& [u, w] : adj[now]) { if (u == to) { W[1][id + 1] = w; } } id++; } } int res = 0; // cout << "\nline = "; // for (int i = 0; i < N; ++i) { // cout << line[i] << " "; // } // cout << "\n"; // cout << "X weights = "; // for (int i = 0; i < N; ++i) { // cout << W[0][i] << " "; // } // cout << "\n"; // cout << "Y weights = "; // for (int i = 0; i < N; ++i) { // cout << W[1][i] << " "; // } // cout << "\n"; cerr << idx[X] << " " << idx[Y] << "\n"; for (int left = 0; left < N; ++left) { ll sum = 0; ll curr = 0; vector<ll> C(N), ps(N); int now = left + 1; int id = idx[X]; bool ok = true; for (int it = 0; it <= left; ++it) { if (id < 0) { ok = false; break; } curr += W[0][id]; if (sum + curr - C[id] > K) { ok = false; break; } sum += curr - C[id]; C[id] = curr; ps[id] = curr; id -= 1; } if (!ok) continue; curr = 0; id = idx[X]; vector<array<ll, 3>> rollback; int leftid = idx[Y], rightid = idx[Y]; ll leftsum = 0, rightsum = 0; now += 1; while (true) { ll take_left = K, take_right = K; if (leftid - 1 >= 0) { take_left = max(0LL, leftsum + W[1][leftid - 1] - C[leftid - 1]); } if (rightid + 1 < N) { take_right = max(0LL, rightsum + W[1][rightid + 1] - C[rightid + 1]); } if (sum + min(take_left, take_right) > K) { break; } if (take_left < take_right) { sum += take_left; rollback.push_back({0, C[leftid - 1], take_left}); leftsum += W[1][leftid - 1]; C[leftid - 1] = max(leftsum, C[leftid - 1]); leftid -= 1; } else { sum += take_right; rollback.push_back({1, C[rightid + 1], take_right}); rightsum += W[1][rightid + 1]; C[rightid + 1] = max(rightsum, C[rightid + 1]); rightid += 1; } now += 1; } // cerr << left << " = " << leftid << " " << rightid << "\n"; curr = 0; for (int right = idx[X] + 1; right < N; ++right) { curr += W[0][right]; ll add = max(0LL, curr - C[right]); while (rollback.size() > 0 && sum + add > K) { int p = rollback.back()[0]; ll pC = rollback.back()[1]; ll w = rollback.back()[2]; rollback.pop_back(); if (p == 0) { C[leftid] = pC; sum -= w; if (ps[leftid] > C[leftid]) { sum += ps[leftid] - C[leftid]; C[leftid] = ps[leftid]; } leftid++; } else { sum -= w; C[rightid] = pC; if (ps[rightid] > C[rightid]) { sum += ps[rightid] - C[rightid]; C[rightid] = ps[rightid]; } rightid--; } now -= 1; } sum += add; if (sum > K) continue; C[right] += add; ps[right] = curr; now += 1; res = max(res, now); } } 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...