Submission #1160439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160439		kl0989e	봉쇄 시간 (IOI23_closing)	C++20	43 / 100	73 ms	29764 KiB

closing

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

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;

vector<vector<pi>> graph(maxn);
vl vala(maxn,0);
vl valb(maxn,0);
vl val_cur(maxn,0);
vi prev_a(maxn,-1);
vi prev_b(maxn,-1);

void dfs(int cur, int prev=-1, ll dist=0) {
    prev_a[cur]=prev;
    vala[cur]=dist;
    for (auto [to,add]:graph[cur]) {
        if (to!=prev) {
            dfs(to,cur,dist+add);
        }
    }
}

int max_score(int n, int x, int y, long long k, vi u, vi v, vi w) {
    for (int i=0; i<n; i++) {
        graph[i].clear();
        vala[i]=valb[i]=val_cur[i]=0;
        prev_a[i]=prev_b[i]=-1;
    }
    for (int i=0; i<n-1; i++) {
        graph[u[i]].pb({v[i],w[i]});
        graph[v[i]].pb({u[i],w[i]});
    }
    dfs(y);
    swap(vala,valb);
    swap(prev_a,prev_b);
    dfs(x);
    set<pl> qa={{0,x},{2e18,-1}},qb={{0,y},{2e18,-1}};
    int ans=0;
    while (min(qa.begin()->fi,qb.begin()->fi)<=k) {
        ans++;
        if (qa.begin()->fi<=qb.begin()->fi) {
            auto [val,cur]=*qa.begin();
            qa.erase(qa.begin());
            val_cur[cur]+=val;
            k-=val;
            for (auto [to,add]:graph[cur]) {
                if (to!=prev_a[cur]) {
                    qa.insert({vala[to]-val_cur[to],to});
                }
            }
            if (qb.count({valb[cur],cur})) {
                qb.erase({valb[cur],cur});
                qb.insert({valb[cur]-val_cur[cur],cur});
            }
        }
        else {
            auto [val,cur]=*qb.begin();
            qb.erase(qb.begin());
            val_cur[cur]+=val;
            k-=val;
            for (auto [to,add]:graph[cur]) {
                if (to!=prev_b[cur]) {
                    qb.insert({valb[to]-val_cur[to],to});
                }
            }
            if (qa.count({vala[cur],cur})) {
                qa.erase({vala[cur],cur});
                qa.insert({vala[cur]-val_cur[cur],cur});
            }
        }
    }
    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