제출 #1032435

#제출 시각아이디문제언어결과실행 시간메모리
1032435Turkhuu봉쇄 시간 (IOI23_closing)C++17
51 / 100
1073 ms2097152 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) { vector<vector<array<int, 2>>> 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]}); } auto bfs = [&](int s) { vector<ll> dis(N); vector<int> from(N, -1); from[s] = s; queue<int> q; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); for (auto [y, z] : adj[x]) { if (from[y] == -1) { from[y] = x; dis[y] = dis[x] + z; q.push(y); } } } return make_pair(dis, from); }; auto [dis_x, from_x] = bfs(X); auto [dis_y, from_y] = bfs(Y); vector<ll> one(N), two(N); for (int i = 0; i < N; i++) { tie(one[i], two[i]) = minmax(dis_x[i], dis_y[i]); } int ans = 0; { auto a(one); sort(a.begin(), a.end()); ll sum = 0; while (ans < N && sum + a[ans] <= K) sum += a[ans++]; } vector<int> path{X}; while (path.back() != Y) path.push_back(from_y[path.back()]); int M = path.size(); vector<int> on_path(N); for (auto x : path) on_path[x] = 1; vector dp(N, vector(3, vector<ll>(2 * N + 1, 1e18))); function<void(int, int)> dfs = [&](int x, int p) { dp[x][1][1] = one[x]; dp[x][2][2] = two[x]; for (auto [y, z] : adj[x]) { if (y == p || on_path[y]) continue; dfs(y, x); for (int i = 2 * N; i >= 0; i--) { for (int j = i - 1; j >= 0; j--) { dp[x][1][i] = min(dp[x][1][i], dp[y][1][i - j] + dp[x][1][j]); dp[x][2][i] = min(dp[x][2][i], min(dp[y][1][j], dp[y][2][j]) + dp[x][2][i - j]); } } } }; for (auto x : path) dfs(x, -1); // for (int i = 0; i < M; i++) { // int x = path[i]; // cout << x + 1 << ":-----------------\n"; // for (int j = 1; j <= 2; j++) { // cout << " " << j << ":\n"; // for (int k = 0; k <= 2 * N; k++) { // if (dp[x][j][k] != 1e18) { // cout << " " << k << " " << dp[x][j][k] << "\n"; // } // } // } // } vector f(M + 1, vector(3, vector<ll>(2 * N + 1, 1e18))); f[0][0][0] = 0; for (int i = 1; i <= M; i++) { int x = path[i - 1]; for (int j = 0; j <= 2 * N; j++) { for (int k = j; k <= 2 * N; k++) { f[i][0][k] = min(f[i][0][k], f[i - 1][0][j] + dp[x][1][k - j]); f[i][2][k] = min(f[i][2][k], min(f[i - 1][0][j], f[i - 1][2][j]) + dp[x][2][k - j]); f[i][1][k] = min(f[i][1][k], min(f[i - 1][1][j], f[i - 1][2][j]) + dp[x][1][k - j]); } } } for (int i = 2 * N; i >= 0; i--) { if (f[M][1][i] <= K || f[M][2][i] <= K) { ans = max(ans, 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...