Submission #1160452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160452		kl0989e	Closing Time (IOI23_closing)	C++20	43 / 100	80 ms	30532 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);
vi seen(maxn,0);

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;
        seen[i]=0;
    }
    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<array<ll,3>> qa={{0,valb[x],x},{(ll)(2e18+1),0,-1}},qb={{0,vala[y],y},{(ll)(2e18+1),0,-1}};
    int ans=0;
    while (min((*qa.begin())[0],(*qb.begin())[0])<=k) {
        ans++;
        if ((*qa.begin())[0]<(*qb.begin())[0] || ((*qa.begin())[0]==(*qb.begin())[0] && (*qa.begin())[1]<=(*qb.begin())[1])) {
            auto temp=*qa.begin();
            ll val=temp[0],_=temp[1],cur=temp[2];
            seen[cur]=1;
            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],(seen[to]?(ll)(2e18+1):valb[to]),to});
                }
            }
            if (qb.count({valb[cur],vala[cur],cur})) {
                qb.erase({valb[cur],vala[cur],cur});
                qb.insert({valb[cur]-val_cur[cur],(ll)(2e18+1),cur});
            }
        }
        else {
            auto temp=*qb.begin();
            ll val=temp[0],_=temp[1],cur=temp[2];
            seen[cur]=1;
            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],(seen[to]?(ll)(2e18+1):vala[to]),to});
                }
            }
            if (qa.count({vala[cur],valb[cur],cur})) {
                qa.erase({vala[cur],valb[cur],cur});
                qa.insert({vala[cur]-val_cur[cur],(ll)(2e18+1),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