Submission #1056675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056675		mc061	Closing Time (IOI23_closing)	C++17	0 / 100	876 ms	2097152 KiB

closing

#include <bits/stdc++.h>
using namespace std;
 
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    const int n = N;
    vector<vector<pair<int, int>>> tree(n);
    for (int i = 0; i < n - 1; ++i) {
        tree[V[i]].push_back({U[i], W[i]});
        tree[U[i]].push_back({V[i], W[i]});
    }
    vector<int64_t> dx(n), dy(n);
    auto dfs = [&] (auto&& self, int v, vector<int64_t>& dist, int p = -1, int64_t d = 0) -> void {
        dist[v] = d;
        for (auto [u, w] : tree[v]) {
            if (u == p) continue;
            self(self, u, dist, v, d + w);
        }
    };
    dfs(dfs, X, dx);
    dfs(dfs, Y, dy);
 
    int64_t cost[n][4]={};
    for (int i = 0; i < n; ++i) {
        cost[i][0] = 0;
        cost[i][1] = dx[i];
        cost[i][2] = dy[i];
        cost[i][3] = max(dx[i], dy[i]);
    }
 
    int64_t dp[n][2*n+1][4]={};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2*n+1; ++j) {
            fill(dp[i][j], dp[i][j]+4, 1e18+1);
        }
    }
    bool can_trans[4][4]={};
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            can_trans[i][j] = true;
        }
    }
    dp[0][0][0] = 0;
    dp[0][1][1] = cost[0][1];
    dp[0][2][1] = cost[0][2];
    dp[0][3][2] = cost[0][3];
    for (int i = 1; i < n; ++i) {
        if (i > X) {
            can_trans[0][1] = false;
            can_trans[0][3] = false;
        }
        if (i > Y) {
            can_trans[0][2] = false;
            can_trans[0][3] = false;
        }
        for (int j = 0; j < 2*n+1; ++j) {
            dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]);
            if (i > X)
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][1]);
            if (i > Y)
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][2]);
            if (i > Y)
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][3]);
            if (can_trans[0][1] && j>0)
                dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][0] + cost[i][1]);
            if (can_trans[0][2] && j>0)
                dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][0] + cost[i][2]);
            if (j>0) {
                dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][1] + cost[i][1]);
                dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][3] + cost[i][1]);
                dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][2] + cost[i][2]);
                dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][3] + cost[i][2]);
            }
            if (can_trans[0][3] && j>1) {
                dp[i][j][3] = min(dp[i][j][3], dp[i-1][j-2][0] + cost[i][3]);   
            }
            if (i <= Y && i >= X && j>1) {
                dp[i][j][3] = min(dp[i][j][3], dp[i-1][j-2][1] + cost[i][3]);
            }
        }
    }
    for (int i = 2*n; i >= 0; --i) {
        if (*min_element(dp[n-1][i], dp[n-1][i]+4) <= K) return i;
    }
    return 0;
}   

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17