제출 #1222315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222315		LucaIlie	봉쇄 시간 (IOI23_closing)	C++17	43 / 100	134 ms	54772 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 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 lastX = 0;
    for (int i = 0; i < m; i++) {
        int v = path[i];
        if (distX[v] <= distY[v])
            lastX = i;
    }

    int maxScore = 0;
    for (int takeAllX = 0; takeAllX < 2; takeAllX++) {
        for (int takeAllY = 0; takeAllY < 2; takeAllY++) {
            if (takeAllX != takeAllY)
                continue;
            
            for (int v = 0; v < n; v++) 
                level[v] = 0;

            int score = 0;
            long long c = 0;
            if (takeAllX) {
                for (int i = 0; i <= lastX; i++) {
                    int v = path[i];
                    c += distX[v];
                    level[v] = 1;
                    score++;
                }
            } 
            if (takeAllY) {
                for (int i = lastX + 1; i < m; i++) {
                    int v = path[i];
                    c += distY[v];
                    level[v] = 1;
                    score++;
                }
            }

            priority_queue<aaa> pq;
            for (int v = 0; v < n; v++)  {
                // printf("%d %d\n", v, level[v]);
                if (level[v] == 0)
                    pq.push({1, v, cost1[v]});
                else if (((distX[v] <= distY[v] && takeAllY) ||
                                    (distX[v] > distY[v] && takeAllX)))
                    pq.push({2, v, upgrade[v]});
            }

            if (c > k)
                continue;

            while (!pq.empty() && c + pq.top().c <= k) {
                auto p = pq.top();
                pq.pop();

                // printf("%d %d %lld\n", p.t, p.v, p.c);
                int v = p.v;
                c += p.c;
                level[v] = p.t;
                score++;

                if (level[v] == 1 && ((distX[v] <= distY[v] && takeAllY) ||
                                    (distX[v] > distY[v] && takeAllX)))
                    pq.push({2, v, upgrade[v]});
            }

            maxScore = max(maxScore, score);

            // printf("%d %d -> %d\n", takeAllX, takeAllY, 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: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17