Submission #844551

#	Time	Username	Problem	Language	Result	Execution time	Memory
844551		gingers	Closing Time (IOI23_closing)	C++17	8 / 100	255 ms	41296 KiB

closing

#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii=pair <long long,long long>;
using rii=pair <long long,pii>;
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
    #define x first
    #define y second
    #define pb push_back
    #define int long long
    vector <pii> g[N];
    for (int i=0; i<N-1; i++){
        g[U[i]].pb({V[i],W[i]});
        g[V[i]].pb({U[i],W[i]});
    }
    int distX[N],distY[N],prvX[N];
    bool visited[N];
    for (int i=0; i<N; i++) visited[i]=0;
    distX[X]=0; visited[X]=1; prvX[X]=X;
    queue <int> q;
    q.push(X);
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (pii i:g[tp]){
            if (visited[i.x]) continue;
            distX[i.x]=distX[tp]+i.y;
            visited[i.x]=1;
            prvX[i.x]=tp;
            q.push(i.x);
        }
    }
    for (int i=0; i<N; i++) visited[i]=0;
    distY[Y]=0; visited[Y]=1;
    q.push(Y);
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (pii i:g[tp]){
            if (visited[i.x]) continue;
            distY[i.x]=distY[tp]+i.y;
            visited[i.x]=1;
            q.push(i.x);
        }
    }
    int ans=0;
    {
        int k=K;
        priority_queue <rii,vector <rii>,greater <rii> > pq;
        pq.push({0,{X,0}});
        pq.push({0,{Y,1}});
        while (!pq.empty()&&k>=0){
            rii tp=pq.top(); pq.pop();
            if (k<tp.x) break;
            k-=tp.x;
            ans++;
            if (!tp.y.y){
                for (auto i:g[tp.y.x]){
                    if (distX[i.x]>distX[tp.y.x]){
                        pq.push({distX[i.x],{i.x,0}});
                    }
                }
            } else {
                for (auto i:g[tp.y.x]){
                    if (distY[i.x]>distY[tp.y.x]){
                        pq.push({distY[i.x],{i.x,1}});
                    }
                }
            }
        }
    }
    vector <int> path;
    path.pb(Y);
    while (path.back()!=X) path.pb(prvX[path.back()]);
    reverse(path.begin(),path.end());
    set <int> spath;
    for (int i:path) spath.insert(i);
    {
        int ths=0,k=K;
        priority_queue <rii,vector <rii>,greater <rii> > pq;
        bool doneX[N],doneY[N];
        int bel[N];
        for (int i=0; i<N; i++) doneX[i]=doneY[i]=0;
        for (int i=0; i<N; i++) bel[i]=0;
        int f=-1,l=-1;
        for (int i:path){
            if (2*distX[i]<=distX[Y]){
                doneX[i]=1;
                k-=distX[i];
                ths++;
                for (pii j:g[i]){
                    if (spath.find(j.x)!=spath.end()) continue;
                    pq.push({distX[j.x],{j.x,0}});
                }
                bel[i]=0;
                visited[i]=1;
                q.push(i);
                f=i;
            } else {
                doneY[i]=1;
                k-=distY[i];
                ths++;
                for (pii j:g[i]){
                    if (spath.find(j.x)!=spath.end()) continue;
                    pq.push({distY[j.x],{j.x,1}});
                }
                bel[i]=1;
                visited[i]=1;
                q.push(i);
                if (l==-1) l=i;
            }
        }
        while (!q.empty()){
            int tp=q.front(); q.pop();
            for (pii i:g[tp]){
                if (visited[i.x]) continue;
                visited[i.x]=1;
                bel[i.x]=bel[tp];
                q.push(i.x);
            }
        }
        pq.push({distX[l]-distY[l],{l,0}});
        pq.push({distY[f]-distX[f],{f,1}});
        while (!pq.empty()&&k>=0){
            rii tp=pq.top(); pq.pop();
            if (k<tp.x) break;
            k-=tp.x;
            ths++;
            if (!tp.y.y){
                for (pii i:g[tp.y.x]){
                    if (doneX[i.x]) continue;
                    doneX[i.x]=1;
                    pq.push({distX[i.x]-distY[i.x]*bel[i.x],{i.x,0}});
                }
            } else {
                for (pii i:g[tp.y.x]){
                    if (doneY[i.x]) continue;
                    doneY[i.x]=1;
                    pq.push({distY[i.x]-distX[i.x]*(1-bel[i.x]),{i.x,1}});
                }
            }
        }
        if (k>=0) ans=max(ans,ths);
    }
    return ans;
    #undef x
    #undef y
    #undef pb
    #undef int
}

• 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