제출 #902637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902637		jamesbamber	봉쇄 시간 (IOI23_closing)	C++17	43 / 100	998 ms	33188 KiB

closing

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

typedef long long ll;

vector<vector<pair<int,ll>>> ad;
vector<int> on_path;
int n;

vector<pair<int, ll>> find_path(int s, int e){
    
    vector<pair<int, ll>> prv(n, {-1, -1});

    queue<int> q; q.push(e);
    while(q.size()){
        int v = q.front(); q.pop();
        for(auto [u, w]: ad[v]){
            if(u == prv[v].first) continue;
            prv[u] = {v, w};
            q.push(u);
        }
    }
    vector<pair<int, ll>> path; 
    pair<int, ll> v = {s, 0};
    while(v.first != -1){
        path.push_back(v);
        v = prv[v.first];
    }
    return path;
}   

int calc_sus(ll k, ll t, priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> &pq){
    
    int ct = 0;
    while(pq.size()){
        auto [c, diff, v, prv] = pq.top(); pq.pop();
        if(diff > t or diff == -1) c/=2;
        if(k-c < 0) continue; 
        if(diff == -1){
            k -= c;
            ct++;
            continue;
        }
        if(prv != -1){
            k -= c;
            ct++; 
            if(diff <= t) ct++;
        }
        if(diff > t) pq.push({2*diff, -1, -1, -1});

        for(auto [u, w]: ad[v]){
            if(on_path[u] or u == prv) continue;
            if(diff <= t) pq.push({c+w, diff, u, v});
            else pq.push({(c+w)*2, diff, u, v});
        }
    }
    return ct;
}

int greedy(ll k, int s1, int s2){
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> pq;
    pq.push({0, s1, -1}); pq.push({0, s2, -1});
    int ct = 0;
    while(pq.size()){
        auto [c, v, prv] = pq.top(); pq.pop();
        if(k-c < 0) return ct;
        k -= c; ct++;

        for(auto [u, w]: ad[v]){
            if(u == prv) continue;
            pq.push({c+w, u, v});
        }
    }
    return ct;
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N;
    ad.assign(N, vector<pair<int,ll>>());
    for(int i=0; i<N-1; i++){
        ad[U[i]].push_back({V[i], W[i]});
        ad[V[i]].push_back({U[i], W[i]});
    }

    vector<pair<int, ll>> path = find_path(X, Y);
    on_path.assign(N, 0); for(auto [a, b]: path) on_path[a] = 1;
    vector<ll> diff(N), dist(N);

    ll tot = 0, sum = 0;
    for(auto [a, b]: path) tot += b;

    set<ll> checkdiff; checkdiff.insert(0);
    for(auto [a, b]: path){
        sum += b;
        diff[a] = abs(2*sum - tot);
        dist[a] = min(sum, tot-sum);
        checkdiff.insert(diff[a]);
    }

    int ans = greedy(K, X, Y);
    if(tot > K*2) return ans;


    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
    for(ll t: checkdiff){
        while(pq.size()) pq.pop();
        ll k = K;
        int ct = 0;
        for(auto [c, d]: path){
            if(diff[c] <= t) pq.push({dist[c]+diff[c], diff[c], c, -1}), ct+=2, k-= dist[c]+diff[c];
            else pq.push({2*dist[c], diff[c], c, -1}), ct++, k-= dist[c];
        }
        if(k < 0) continue;
        ans = max(ans, ct + calc_sus(k, t, pq));
    }

    return ans;
}

• 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