oj.uz

Submission #839706

# Submission time Handle Problem Language Result Execution time Memory
839706 2023-08-30T15:46:12 Z model_code Closing Time (IOI23_closing) C++17
51 / 100
 1000 ms 1817060 KB 
// correct/solution-ayaze-knapsack-optimized.cpp

// O(N^2) with high constant factor
// probably can AC N <= 2000 if optimized e.g using plain array
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

const int kStateX = 1, kStateYActive = 2, kStateYInActive = 4;
const long long kInf = 4e18;

vector<vector<pair<int, int>>> adj_list;
vector<long long> dist_from_x, dist_from_y;
vector<int> size_rooted_x;
vector<bool> in_path;
vector<vector<vector<long long>>> dp_mat;
int N, Y;

void DfsDistance(int now, int prv, long long current_dist,
                 vector<long long> &dist_vec, vector<int> &parent, vector<int> &sz)
{
    dist_vec[now] = current_dist;
    parent[now] = prv;
    sz[now] = 1;

    for (pair<int, int> edge : adj_list[now])
    {
        int nxt = edge.first;
        if (nxt == prv)
            continue;
        long long new_dist = edge.second + current_dist;
        DfsDistance(nxt, now, new_dist, dist_vec, parent, sz);
        sz[now] += sz[nxt];
    }
}

void DfsDP(int now, int prv)
{
    for (int score = 0; score <= 2 * N; score++)
    {
        for (int mask = 0; mask < (1 << 3); mask++)
        {
            dp_mat[now][score][mask] = kInf;
        }
    }

    for (int mask = 0; mask < (1 << 3); mask++)
    {
        if ((mask & kStateYActive) > 0 && (mask & kStateYInActive) > 0)
            continue;

        int score = 0;
        long long val = 0;

        if (mask & kStateX)
            score++, val = max(val, dist_from_x[now]);
        if (mask & kStateYActive)
            score++, val = max(val, dist_from_y[now]);
        dp_mat[now][score][mask] = val;
    }

    int current_sz = 1;

    for (pair<int, int> edge : adj_list[now])
    {
        int nxt = edge.first;
        if (nxt == prv)
            continue;
        DfsDP(nxt, now);

        vector<vector<long long>> copy_current_dp;
        for (int score = 0; score <= 2 * current_sz; score++)
        {
            copy_current_dp.push_back(dp_mat[now][score]);
        }

        int child_sz = size_rooted_x[nxt];
        int new_sz = current_sz + child_sz;
        for (int score = 0; score <= 2 * new_sz; score++)
        {
            for (int mask = 0; mask < (1 << 3); mask++)
            {
                dp_mat[now][score][mask] = kInf;
            }
        }

        for (int score = 0; score <= 2 * current_sz; score++)
        {
            for (int mask = 0; mask < (1 << 3); mask++)
            {
                if ((mask & kStateYActive) > 0 && (mask & kStateYInActive) > 0)
                    continue;

                int active_x = mask & kStateX;
                int upper_mask = mask - active_x;
                for (int child_score = 0; child_score <= 2 * child_sz && child_score + score <= 2 * new_sz; child_score++)
                {
                    for (int state_x = 0; state_x <= active_x; state_x++)
                    { // we can keep X, or turn it off
                        // Y state do not change
                        dp_mat[now][score + child_score][mask] = min(
                            copy_current_dp[score][mask] + dp_mat[nxt][child_score][state_x | upper_mask],
                            dp_mat[now][score + child_score][mask]);
                        // currently reachable by Y, make child unreachable by Y
                        if (mask & kStateYActive)
                        {
                            dp_mat[now][score + child_score][mask] = min(
                                copy_current_dp[score][mask] + dp_mat[nxt][child_score][state_x],
                                dp_mat[now][score + child_score][mask]);
                        }
                        // this and above not reachable by Y,
                        // from here downward make it possible to be reachable by Y
                        if ((mask & kStateYInActive) > 0 && in_path[nxt])
                        {
                            dp_mat[now][score + child_score][mask] = min(
                                copy_current_dp[score][mask] + dp_mat[nxt][child_score][state_x | kStateYActive],
                                dp_mat[now][score + child_score][mask]);
                        }
                    }
                }
            }
        }

        current_sz = new_sz;
    }

    // if it is Y, then it must be reachable by Y
    if (now == Y)
    {
        for (int score = 0; score <= 2 * current_sz; score++)
        {
            for (int mask = 0; mask < (1 << 3); mask++)
            {
                if ((mask & kStateYActive) == 0)
                {
                    dp_mat[now][score][mask] = kInf;
                }
            }
        }
    }
}

int max_score(int _N, int X, int _Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    N = _N;
    Y = _Y;

    adj_list.assign(N, vector<pair<int, int>>());
    dist_from_x.resize(N);
    dist_from_y.resize(N);
    in_path.assign(N, false);
    dp_mat.assign(N, vector<vector<long long>>(2 * N + 1, vector<long long>(1 << 3, 0)));
    size_rooted_x.assign(N, 0);

    for (int i = 0; i < static_cast<int>(U.size()); i++)
    {
        adj_list[U[i]].push_back({V[i], W[i]});
        adj_list[V[i]].push_back({U[i], W[i]});
    }

    vector<int> parent_rooted_x(N);
    DfsDistance(Y, -1, 0, dist_from_y, parent_rooted_x, size_rooted_x);
    DfsDistance(X, -1, 0, dist_from_x, parent_rooted_x, size_rooted_x);
    for (int i = Y; i != X; i = parent_rooted_x[i])
    {
        in_path[i] = true;
    }

    DfsDP(X, -1);
    int ret = 0;
    for (int score = 0; score <= 2 * N; score++)
    {
        for (int mask = 0; mask < (1 << 3); mask++)
        {
            if (dp_mat[X][score][mask] <= K)
            {
                ret = max(ret, score);
            }
        }
    }

    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1166 ms 1090568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 680 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 812 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 680 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 812 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 4 ms 2344 KB Output is correct
14 Correct 3 ms 1968 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 3 ms 2344 KB Output is correct
17 Correct 2 ms 2388 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 59 ms 51440 KB Output is correct
20 Correct 50 ms 43032 KB Output is correct
21 Correct 58 ms 47200 KB Output is correct
22 Correct 67 ms 51044 KB Output is correct
23 Correct 63 ms 51428 KB Output is correct
24 Correct 76 ms 51504 KB Output is correct

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 680 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 812 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 4 ms 2344 KB Output is correct
14 Correct 3 ms 1968 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 3 ms 2344 KB Output is correct
17 Correct 2 ms 2388 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 59 ms 51440 KB Output is correct
20 Correct 50 ms 43032 KB Output is correct
21 Correct 58 ms 47200 KB Output is correct
22 Correct 67 ms 51044 KB Output is correct
23 Correct 63 ms 51428 KB Output is correct
24 Correct 76 ms 51504 KB Output is correct
25 Correct 14 ms 904 KB Output is correct
26 Execution timed out 1158 ms 1817060 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 300 KB Output is correct
24 Correct 1 ms 340 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 812 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 4 ms 2344 KB Output is correct
15 Correct 3 ms 1968 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2344 KB Output is correct
18 Correct 2 ms 2388 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 216 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 300 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 596 KB Output is correct
39 Correct 2 ms 2260 KB Output is correct
40 Correct 3 ms 2132 KB Output is correct
41 Correct 3 ms 2260 KB Output is correct
42 Correct 2 ms 2132 KB Output is correct
43 Correct 3 ms 2004 KB Output is correct
44 Correct 2 ms 2132 KB Output is correct
45 Correct 3 ms 2260 KB Output is correct
46 Correct 2 ms 2260 KB Output is correct
47 Correct 3 ms 2260 KB Output is correct
48 Correct 3 ms 1748 KB Output is correct
49 Correct 1 ms 940 KB Output is correct
50 Correct 1 ms 468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 812 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 4 ms 2344 KB Output is correct
15 Correct 3 ms 1968 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2344 KB Output is correct
18 Correct 2 ms 2388 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 59 ms 51440 KB Output is correct
21 Correct 50 ms 43032 KB Output is correct
22 Correct 58 ms 47200 KB Output is correct
23 Correct 67 ms 51044 KB Output is correct
24 Correct 63 ms 51428 KB Output is correct
25 Correct 76 ms 51504 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 216 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 304 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 300 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 596 KB Output is correct
46 Correct 2 ms 2260 KB Output is correct
47 Correct 3 ms 2132 KB Output is correct
48 Correct 3 ms 2260 KB Output is correct
49 Correct 2 ms 2132 KB Output is correct
50 Correct 3 ms 2004 KB Output is correct
51 Correct 2 ms 2132 KB Output is correct
52 Correct 3 ms 2260 KB Output is correct
53 Correct 2 ms 2260 KB Output is correct
54 Correct 3 ms 2260 KB Output is correct
55 Correct 3 ms 1748 KB Output is correct
56 Correct 1 ms 940 KB Output is correct
57 Correct 1 ms 468 KB Output is correct
58 Correct 4 ms 596 KB Output is correct
59 Correct 8 ms 3848 KB Output is correct
60 Correct 6 ms 2404 KB Output is correct
61 Correct 11 ms 4964 KB Output is correct
62 Correct 10 ms 4948 KB Output is correct
63 Correct 55 ms 51272 KB Output is correct
64 Correct 52 ms 44688 KB Output is correct
65 Correct 42 ms 42248 KB Output is correct
66 Correct 51 ms 45244 KB Output is correct
67 Correct 54 ms 50512 KB Output is correct
68 Correct 54 ms 42520 KB Output is correct
69 Correct 65 ms 50624 KB Output is correct
70 Correct 53 ms 47208 KB Output is correct
71 Correct 50 ms 46264 KB Output is correct
72 Correct 54 ms 48156 KB Output is correct
73 Correct 41 ms 31392 KB Output is correct
74 Correct 47 ms 35028 KB Output is correct
75 Correct 7 ms 3756 KB Output is correct

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 812 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 4 ms 2344 KB Output is correct
15 Correct 3 ms 1968 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2344 KB Output is correct
18 Correct 2 ms 2388 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 59 ms 51440 KB Output is correct
21 Correct 50 ms 43032 KB Output is correct
22 Correct 58 ms 47200 KB Output is correct
23 Correct 67 ms 51044 KB Output is correct
24 Correct 63 ms 51428 KB Output is correct
25 Correct 76 ms 51504 KB Output is correct
26 Correct 14 ms 904 KB Output is correct
27 Execution timed out 1158 ms 1817060 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 812 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 4 ms 2344 KB Output is correct
15 Correct 3 ms 1968 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2344 KB Output is correct
18 Correct 2 ms 2388 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 59 ms 51440 KB Output is correct
21 Correct 50 ms 43032 KB Output is correct
22 Correct 58 ms 47200 KB Output is correct
23 Correct 67 ms 51044 KB Output is correct
24 Correct 63 ms 51428 KB Output is correct
25 Correct 76 ms 51504 KB Output is correct
26 Correct 14 ms 904 KB Output is correct
27 Execution timed out 1158 ms 1817060 KB Time limit exceeded
28 Halted 0 ms 0 KB -