Submission #1056464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056464		TheQuantiX	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	1028 ms	59328 KiB

closing

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

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000000000000LL;

ll n, m, q, k, x, y, a, b, c, d;
map<ll, ll> G[200000];

void dfs(ll x, vector<ll> &dist, ll d) {
    dist[x] = d;
    for (auto i : G[x]) {
        if (dist[i.first] == INF) {
            dfs(i.first, dist, d + i.second);
        }
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    x = X;
    y = Y;
    k = K;
    for (auto i = 0; i < n - 1; i++) {
        G[U[i]][V[i]] = W[i];
        G[V[i]][U[i]] = W[i];
    }
    vector<ll> dist1(n, INF), dist2(n, INF);
    dfs(x, dist1, 0);
    dfs(y, dist2, 0);
    vector<ll> vec;
    for (int i = 0; i < n; i++) {
        // cout << dist1[i] << ' ';
        vec.push_back(dist1[i]);
    }
    // cout << '\n';
    for (int i = 0; i < n; i++) {
        vec.push_back(dist2[i]);
    }
    sort(vec.begin(), vec.end());
    ll cnt = 0;
    for (auto i : vec) {
        // cout << i << '\n';
        if (k >= i) {
            cnt++;
            k -= i;
        }
        else {
            break;
        }
    }
    return cnt;
}

• 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