oj.uz

답안 #1056675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056675 2024-08-13T10:34:24 Z mc061 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 876 ms 2097152 KB 
#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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 876 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -