Submission #842084

#	Time	Username	Problem	Language	Result	Execution time	Memory
842084		cjoa	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	57 ms	15304 KiB

closing

#include "closing.h"

#include <vector>
#include <algorithm>
#include <queue>

#include <iostream>

using namespace std;

using llong = long long;

const llong INF = 4e18;

struct Edge {
    int u, v, w;
    int opp(int x) const {
        return x == u ? v : u;
    }
};

vector<Edge> edges;
vector< vector<int> > tree;

llong K;
void dfs(int u, int p, llong t, vector<llong>& closing_times) {
    if (t > K)
        return;
    closing_times[u] = t;
    for (int eid : tree[u]) {
        int v = edges[eid].opp(u);
        if (v == p) continue;
        int w = edges[eid].w;
        dfs(v, u, t + w, closing_times);
    }
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    ::K = K;
//  cerr << "K: " << K << endl;

    tree = vector< vector<int> >(N);
    for (int j = 0; j < N-1; j++) {
        int u = U[j], v = V[j], w = W[j];
        edges.push_back({u, v, w});
    }

    // subtask1

    vector<llong> closing_timesX(N, INF);
    dfs(X, -1, 0, closing_timesX);

    vector<llong> closing_timesY(N, INF);
    dfs(Y, -1, 0, closing_timesY);

    priority_queue<llong> pq;
    llong sum = 0;
    for (int u = 0; u < N; ++u) {
        llong t = min(closing_timesX[u], closing_timesY[u]);
        if (t <= K) {
            pq.push(t);
            sum += t;
        }
    }

    while (sum > K) {
        llong t = pq.top(); pq.pop();
        sum -= t;
    }

    return pq.size();
}

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