Submission #1222347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222347		LucaIlie	Closing Time (IOI23_closing)	C++17	75 / 100	1096 ms	44660 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c;

    int other(int x) {
        return u ^ v ^ x;
    }
};

struct aaa {
    int t, v;
    long long c;

    bool operator < (const aaa &x) const {
        return x.c < c;
    }
};

const int MAX_N = 2e5;
edge edges[MAX_N];
vector<int> adj[MAX_N];
int parent[MAX_N];
vector<int> path;
vector<int> subtree[MAX_N];
bool onPath[MAX_N];
int level[MAX_N];
long long dp[2 * MAX_N + 1];
long long distX[MAX_N], distY[MAX_N];
long long cost1[MAX_N], upgrade[MAX_N];
long long paid[MAX_N];

void calcDist(int u, int p, long long dist[]) {
    // printf("aa %d %d %lld\n", u, p, dist[u]);
    parent[u] = p;
    for (int e: adj[u]) {
        int v = edges[e].other(u), c = edges[e].c;
        if (v == p)
            continue;
        dist[v] = dist[u] + c;
        calcDist(v, u, dist);
    }
}

void findSubtree(int u, int p, int w) {
    subtree[w].push_back(u);
    for (int e: adj[u]) {
        int v = edges[e].other(u);
        if (v == p || onPath[v])
            continue;
        findSubtree(v, u, w);
    }
}

int max_score(int n, int x, int y, long long k, 
                vector<int> U, vector<int> V, vector<int> W) {

    for (int v = 0; v < n; v++) {
        adj[v].clear();
        subtree[v].clear();
        parent[v] = 0;
        distX[v] = distY[v] = 0;
        onPath[v] = false;
        path.clear();
    }
    for (int e = 0; e < n - 1; e++) {
        adj[U[e]].push_back(e);
        adj[V[e]].push_back(e);
        edges[e] = {U[e], V[e], W[e]};
    }

    calcDist(x, -1, distX);
    calcDist(y, -1, distY);

    int v = x;
    while (v != y) {
        path.push_back(v);
        onPath[v] = true;
        v = parent[v];
    }
    path.push_back(y);
    onPath[y] = true;
    int m = path.size();

    for (int v = 0; v < n; v++) {
        cost1[v] = min(distX[v], distY[v]);
        upgrade[v] = max(distX[v], distY[v]) - cost1[v];
    }

    for (int i = 0; i < m; i++)
        findSubtree(path[i], -1, path[i]);

    // for (int v = 0; v < n; v++)
    //     printf("%d %lld %lld\n", v, distX[v], distY[v]);
    // for (int v = 0; v < n; v++)
    //     printf("%d %lld %lld\n", v, cost1[v], upgrade[v]);

    int maxScore = 0;
    for (int takeAll = 0; takeAll < 2; takeAll++) {
        for (int s = 2 * n; s >= 1; s--)
            dp[s] = 1e18;
        dp[0] = 0;
        long long c = 0;
        int s = 0;
        for (int v = 0; v < n; v++) {
            if (onPath[v] && takeAll) {
                c += cost1[v];
                s++;
            }
            for (int s = 2 * n; s >= 0; s--) {
                if (onPath[v] && takeAll) { 
                    if (s >= 1)
                        dp[s] = min(dp[s], dp[s - 1] + upgrade[v]);
                }
                else {
                    if (s >= 1)
                        dp[s] = min(dp[s], dp[s - 1] + cost1[v]);
                    if (takeAll && s >= 2)
                        dp[s] = min(dp[s], dp[s - 2] + cost1[v] + upgrade[v]);
                }
            }
            // for (int s = 0; s <= 2 * n; s++)
            //     printf("%lld ", dp[s]);
            // printf("\n");

        }

        if (c > k)
            continue;

        int score = 0;
        // printf("%lld %d\n", c, s);
        while (score + 1 <= 2 * n && dp[score + 1] <= k - c)
            score++;
        score += s;

        maxScore = max(maxScore, score);
    }


    for (int v = 0; v < n; v++) {
        adj[v].clear();
        subtree[v].clear();
        parent[v] = 0;
        distX[v] = distY[v] = 0;
        onPath[v] = false;
        path.clear();
    }

    return maxScore;
}

• 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