Submission #1213812

#TimeUsernameProblemLanguageResultExecution timeMemory
1213812trimkusClosing Time (IOI23_closing)C++20
75 / 100
1096 ms68840 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<vector<ll>> dist(2, vector<ll>(N)); vector<int> path, current; auto dfs = [&](auto& dfs, int v, int p, int i) -> void { current.push_back(v); if (v == Y && i == 0) { path = current; } for (auto& [u, w] : adj[v]) { if (u == p) continue; dist[i][u] = dist[i][v] + w; dfs(dfs, u, v, i); } current.pop_back(); }; dfs(dfs, X, -1, 0); dfs(dfs, Y, -1, 1); vector<array<ll, 2>> cost; for (int i = 0; i < N; ++i) { ll c1 = min(dist[0][i], dist[1][i]); ll c2 = max(dist[0][i], dist[1][i]); cost.push_back({c1, i}); cost.push_back({c2, i}); } ll tot = 0; int res = 0; vector<bool> vis(N); sort(begin(cost), end(cost)); for (int i = 0; i < (int)cost.size(); ++i) { ll c = cost[i][0]; int j = cost[i][1]; if (vis[j]) { c -= min(dist[0][j], dist[1][j]); } if (tot + c <= K) { tot += c; res += 1; vis[j] = true; } else { break; } } vector<bool> free(N); // cout << "Path = "; for (auto& u : path) { // cout << u << " "; free[u] = true; } // cout << "\n"; int m = 0; while (m + 1 < (int)path.size() && dist[0][path[m + 1]] < dist[1][path[m + 1]]) m++; vector<vector<ll>> DP(2); auto merge = [&](vector<ll> a, vector<ll>& b) -> vector<ll> { vector<ll> res(a.size() + b.size() - 1, K + 1); for (int i = 0; i < (int)a.size(); ++i) { for (int j = 0; j < (int)b.size(); ++j) { res[i + j] = min(res[i + j], a[i] + b[j]); } } return res; }; auto solve = [&](auto& solve, int way, int v, int p) -> array<vector<ll>, 2> { vector<vector<ll>> dp = {{0}, {0}}; for (auto [u, _] : adj[v]) { if (u == p) continue; array<vector<ll>, 2> now = solve(solve, way, u, v); dp[0] = merge(dp[0], now[0]); dp[1] = merge(dp[1], now[1]); } array<vector<ll>, 2> ndp; ndp[0] = {0}; ndp[1] = {0}; ll opt1 = dist[way][v], opt2 = dist[way ^ 1][v]; assert(opt1 <= opt2); int fr = 0; if (free[v]) { fr = 1; opt2 -= opt1; opt1 = 0; } for (int i = 0; i < dp[0].size(); ++i) { int nxt = i + 1 - fr; while (ndp[0].size() <= nxt) ndp[0].push_back(K + 1); while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1); auto& _ndp0 = ndp[0][nxt]; _ndp0 = min(_ndp0, dp[0][i] + opt1); _ndp0 = min(_ndp0, K + 1); auto& _ndp = ndp[1][nxt]; _ndp = min(_ndp, dp[0][i] + opt1); _ndp = min(_ndp, K + 1); } for (int i = 0; i < dp[1].size(); ++i) { int nxt = i + 2 - fr; while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1); auto& _ndp = ndp[1][nxt]; _ndp = min(_ndp, dp[1][i] + opt2); _ndp = min(_ndp, K + 1); } return ndp; }; // cout << "PATH = " << path[m] << " " << path[m + 1] << "\n"; DP[0] = solve(solve, 0, path[m], path[m + 1])[1]; DP[1] = solve(solve, 1, path[m + 1], path[m])[1]; ll add = 0; for (auto& u : path) { add += min(dist[0][u], dist[1][u]); } auto fin = merge(DP[0], DP[1]); for (int i = 0; i < (int)fin.size(); ++i) { // cerr << add << " + " << fin[i] << " = " << i + (int)path.size() << "\n"; if (add + fin[i] <= K) { res = max(res, i + (int)path.size()); } } 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...