Submission #1213812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213812		trimkus	Closing Time (IOI23_closing)	C++20	75 / 100	1096 ms	68840 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> _W)
{
    vector<vector<pair<int, int>>> 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]});
    }
    vector<vector<ll>> dist(2, vector<ll>(N));
    vector<int> path, current;
    auto dfs = [&](auto& dfs, int v, int p, int i) -> void {
        current.push_back(v);
        if (v == Y && i == 0) {
            path = current;
        }
        for (auto& [u, w] : adj[v]) {
            if (u == p) continue;
            dist[i][u] = dist[i][v] + w;
            dfs(dfs, u, v, i);
        }
        current.pop_back();
    };
    dfs(dfs, X, -1, 0);
    dfs(dfs, Y, -1, 1);
    vector<array<ll, 2>> cost;
    for (int i = 0; i < N; ++i) {
        ll c1 = min(dist[0][i], dist[1][i]);
        ll c2 = max(dist[0][i], dist[1][i]);
        cost.push_back({c1, i});
        cost.push_back({c2, i});
    }
    ll tot = 0;
    int res = 0;
    vector<bool> vis(N);
    sort(begin(cost), end(cost));
    for (int i = 0; i < (int)cost.size(); ++i) {
        ll c = cost[i][0];
        int j = cost[i][1];
        if (vis[j]) {
            c -= min(dist[0][j], dist[1][j]);
        }
        if (tot + c <= K) {
            tot += c;
            res += 1;
            vis[j] = true;
        } else {
            break;
        }
    }
    vector<bool> free(N);
    // cout << "Path = ";
    for (auto& u : path) {
        // cout << u << " ";
        free[u] = true;
    }
    // cout << "\n";
    int m = 0;
    while (m + 1 < (int)path.size() && dist[0][path[m + 1]] < dist[1][path[m + 1]]) m++;
    vector<vector<ll>> DP(2);
    auto merge = [&](vector<ll> a, vector<ll>& b) -> vector<ll> {
        vector<ll> res(a.size() + b.size() - 1, K + 1);
        for (int i = 0; i < (int)a.size(); ++i) {
            for (int j = 0; j < (int)b.size(); ++j) {
                res[i + j] = min(res[i + j], a[i] + b[j]);
            }
        }
        return res;
    };
    auto solve = [&](auto& solve, int way, int v, int p) -> array<vector<ll>, 2> {
        vector<vector<ll>> dp = {{0}, {0}};
        for (auto [u, _] : adj[v]) {
            if (u == p) continue;
            array<vector<ll>, 2> now = solve(solve, way, u, v);
            dp[0] = merge(dp[0], now[0]);
            dp[1] = merge(dp[1], now[1]);
        }
        array<vector<ll>, 2> ndp;
        ndp[0] = {0};
        ndp[1] = {0};
        ll opt1 = dist[way][v], opt2 = dist[way ^ 1][v];
        assert(opt1 <= opt2);
        int fr = 0;
        if (free[v]) {
            fr = 1;
            opt2 -= opt1;
            opt1 = 0;
        }
        for (int i = 0; i < dp[0].size(); ++i) {
            int nxt = i + 1 - fr;
            while (ndp[0].size() <= nxt) ndp[0].push_back(K + 1);
            while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1);
            auto& _ndp0 = ndp[0][nxt];
            _ndp0 = min(_ndp0, dp[0][i] + opt1);
            _ndp0 = min(_ndp0, K + 1);
            auto& _ndp = ndp[1][nxt];
            _ndp = min(_ndp, dp[0][i] + opt1);
            _ndp = min(_ndp, K + 1);
        }
        for (int i = 0; i < dp[1].size(); ++i) {
            int nxt = i + 2 - fr;
            while (ndp[1].size() <= nxt) ndp[1].push_back(K + 1);
            auto& _ndp = ndp[1][nxt];
            _ndp = min(_ndp, dp[1][i] + opt2);
            _ndp = min(_ndp, K + 1);
        }
        return ndp;
    };
    // cout << "PATH = " << path[m] << " " << path[m + 1] << "\n";
    DP[0] = solve(solve, 0, path[m], path[m + 1])[1];
    DP[1] = solve(solve, 1, path[m + 1], path[m])[1];
    ll add = 0;
    for (auto& u : path) {
        add += min(dist[0][u], dist[1][u]);
    }
    auto fin = merge(DP[0], DP[1]);
    for (int i = 0; i < (int)fin.size(); ++i) {
        // cerr << add << " + " << fin[i] << " = " << i + (int)path.size() << "\n";
        if (add + fin[i] <= K) {
            res = max(res, i + (int)path.size());
        }
    }
    return res;
}

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