Submission #1223711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223711		LucaIlie	Closing Time (IOI23_closing)	C++17	100 / 100	215 ms	59668 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 {
        if (x.c == c)
            return x.t < t;
        return x.c < c;
    }
};

const int MAX_N = 2e5;
const long long INF = 1e18;
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 v = 0; v < n; v++)
            level[v] = 0;

        long long c = 0;
        int score = 0;
        priority_queue<aaa> pq1, pq2;
        for (int v = 0; v < n; v++) {
            if (onPath[v] && takeAll) {
                c += cost1[v];
                level[v] = 1;
                pq1.push({1, v, upgrade[v]});
                score++;
            } else {
                if (takeAll) {
                    if (upgrade[v] >= cost1[v])
                        pq1.push({0, v, cost1[v]});
                    else
                        pq2.push({0, v, cost1[v] + upgrade[v]});
                } else
                    pq1.push({0, v, cost1[v]});
            }
        }

        if (c > k)
            continue;

        bool done = false;
        while (!pq1.empty() && !pq2.empty() && !done) {
            auto p1 = pq1.top();
            pq1.pop();

            auto p2 = pq2.top();
            pq2.pop();

            if (level[p1.v] > p1.t) {
                pq2.push(p2);
                continue;
            }

            if (level[p2.v] > p2.t) {
                pq1.push(p1);
                continue;
            }


            long long c11 = INF;
            while (!pq1.empty() && level[pq1.top().v] != pq1.top().t)
                pq1.pop();
            if (!pq1.empty()) 
                c11 = p1.c + pq1.top().c;
            long long c22 = p2.c;

            // printf("COMPAR %lld %lld\n", c11, c22);

            done = true;
            if (c11 < c22) {
                // auto p11 = pq1.top();
                // pq1.pop();

                if (c + c11 <= k) {
                    done = false;
                    // c += c11;
                    c += p1.c;
                    // score += 2;
                    score++;
                    level[p1.v]++;
                    // level[p11.v]++;
                    // printf("DIN PQ1 %d %d\n", p1.v, p11.v);
                    if (takeAll) {
                        if (p1.t == 0)
                            pq1.push({1, p1.v, upgrade[p1.v]});
                        // if (p11.t == 0)
                        //     pq1.push({1, p11.v, upgrade[p11.v]});
                    }

                } else {
                    pq1.push(p1);
                    // pq1.push(p11);
                }

                pq2.push(p2);
            } else { 
                if (c + c22 <= k) {
                    // printf("DIN PQ2 %d\n", p1.v);
                    done = false;
                    c += c22;
                    score += 2;
                    level[p2.v] = 2;
                } else
                    pq2.push(p2);

                pq1.push(p1);
            }
            // printf("%lld\n", c);
        }

        while (!pq1.empty()) {
            auto p1 = pq1.top();
            pq1.pop();

            if (level[p1.v] > p1.t) 
                continue;

            if (c + p1.c <= k) {
                c += p1.c;
                score++;
                level[p1.v]++;
                if (takeAll && p1.t == 0)
                    pq1.push({1, p1.v, upgrade[p1.v]});
            }
            // printf("%lld\n", c);
        }

        while (!pq2.empty()) {
            auto p2 = pq2.top();
            pq2.pop();

            if (level[p2.v] > 0)
                continue;

            if (c + p2.c <= k) {
                c += p2.c;
                score += 2;
                level[p2.v] = 2;
            }
            // printf("%lld\n", c);
        }

        // printf("%d %d\n", takeAll, score);
        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: 8 / 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: 17 / 17