Submission #1160487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160487		kl0989e	Closing Time (IOI23_closing)	C++20	8 / 100	455 ms	56700 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);

void dfs(int cur, int prev=-1, ll dist=0) {
    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]=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);
    dfs(x);
    set<pl> q={{2e18+1,-1}};
    for (int i=0; i<n; i++) {
        q.insert({min(vala[i],valb[i]),i});
    }
    int ans1=0;
    ll kk=0;
    while (kk+q.begin()->fi<=k) {
        auto [val,_]=*q.begin();
        q.erase(q.begin());
        kk+=val;
        ans1++;
    }
    int ans=0;
    multiset<pl> q_a={{2e18+1,-1},{2e18+1,-1}},q_b={{2e18+1,-1}},q_c={{2e18+1,-1}};
    for (int i=0; i<n; i++) {
        if (vala[i]+valb[i]==vala[y]) {
            k-=min(vala[i],valb[i]);
            ans++;
            q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i});
        }
        else if (min(vala[i],valb[i])<=max(vala[i],valb[i])-min(vala[i],valb[i])) {
            q_a.insert({min(vala[i],valb[i]),i});
            q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i});
        }
        else if (max(vala[i],valb[i])-min(vala[i],valb[i])<min(vala[i],valb[i])) {
            q_b.insert({max(vala[i],valb[i]),i});
            q_c.insert({min(vala[i],valb[i]),i});
        }
    }
    if (k<0) {
        ans=-1e9;
    }
    while (1) {
        ll cst=min(q_b.begin()->fi,q_a.begin()->fi);
        if (cst>k) {
            break;
        }
        if (q_b.begin()->fi<=q_a.begin()->fi+next(q_a.begin())->fi) {
            ans+=2;
            auto [val,cur]=*q_b.begin();
            k-=val;
            q_c.erase({min(vala[cur],valb[cur]),cur});
            q_b.erase(q_b.begin());
        }
        else {
            k-=q_a.begin()->fi;
            ans++;
            q_a.erase(q_a.begin());
        }
    }
    while (q_c.begin()->fi<=k) {
        k-=q_c.begin()->fi;
        q_c.erase(q_c.begin());
        ans++;
    }
    return max(ans,ans1);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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