Submission #839706

#	Time	Username	Problem	Language	Result	Execution time	Memory
839706		model_code	Closing Time (IOI23_closing)	C++17	51 / 100	1166 ms	1817060 KiB

closing

// 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
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17