제출 #1291298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291298		LaMatematica14	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	1098 ms	35988 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<vector<pair<int, long long>>> adj(N);
    for (int i = 0; i < N-1; i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    function<void(int, int, vector<int> &)> dfs = [&](int a, int p, vector<int> &d) {
        for (auto x : adj[a]) {
            if (x.first == p) continue;
            d[x.first] = d[a]+x.second;
            dfs(x.first, a, d);
        }
    };

    vector<int> dx(N, 0), dy(N, 0);
    dfs(X, -1, dx); dfs(Y, -1, dy);

    int best = 0;
    long long sum = 0;
    vector<pair<long long, int>> massi, mini;
    for (int i = 0; i < N; i++) {
        massi.push_back({max(dx[i], dy[i]), i});
        mini.push_back({min(dx[i], dy[i]), i});
    }
    sort(massi.begin(), massi.end());
    sort(mini.begin(), mini.end());
    // senza doppi
    for (auto x : mini) {
        sum += x.first;
        if (sum <= K) best++;
    }

    sum = 0;
    vector<int> tkx(N, 0), tky(N, 0);
    for (int pref = 0; pref < N; pref++) {
        int tot = 2*(pref+1);
        sum += massi[pref].first;
        if (sum > K) break;

        int a = massi[pref].second;
        if (tkx[a]) sum -= dx[a];
        else if (tky[a]) sum -= dy[a];
        tkx[a] = 1; tky[a] = 1;

        // aggiorno i path
        while (a != X) {
            for (auto x : adj[a]) {
                if (dx[a] <= dx[x.first]) continue;
                a = x.first;
                if (tkx[a]) continue;
                tkx[a] = 1;
                sum += dx[a]; 
                tot++;
                break;
            }
        }
        a = massi[pref].second;
        while (a != Y){
            for (auto x : adj[a]) {
                if (dy[a] <= dy[x.first]) continue;
                a = x.first;
                if (tky[a]) continue;
                tky[a] = 1;
                sum += dy[a]; 
                tot++;
                break;
            }
        }
        if (sum > K) break;

        long long currsum = sum;
        // aggiungo i minimi
        for (int i = 0; i < N; i++) {
            int h = mini[i].second;
            if (tkx[h] || tky[h]) continue;
            currsum += mini[i].first;
            if (currsum > K) break;
            tot++;
        }

        best = max(tot, best);
    }
    return best;
}

• 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