제출 #840086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840086		bachhoangxuan	Closing Time (IOI23_closing)	C++17	73 / 100	830 ms	217420 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int maxs=3005;
#define pii pair<int,int>
#define piii pair<long long,pii>
#define fi first
#define se second
const long long inf=2e18;

long long dist[maxn][2];
long long dp2[maxs][2*maxs],dp1[maxs][maxs],nw2[2*maxs],nw1[maxs];
int sz[maxn];

vector<pii> edge[maxn];
bool check[maxn];

bool cc[maxn][2];

int max_score(int n, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{
    for(int i=0;i<n;i++){
        edge[i].clear();check[i]=cc[i][0]=cc[i][1]=false;
        dist[i][0]=dist[i][1]=0;sz[i]=1;
    }

    for(int i=0;i<n-1;i++){
        edge[U[i]].push_back({V[i],W[i]});
        edge[V[i]].push_back({U[i],W[i]});
    }

    vector<int> path;
    function<void(int,int)> pre_dfs = [&](int u,int p){
        if(u==Y){
            path.push_back(u);
            check[u]=true;
            return;
        }
        for(auto &[v,w]:edge[u]){
            if(v==p) continue;
            pre_dfs(v,u);check[u]|=check[v];
        }
        if(check[u]) path.push_back(u);
    };
    pre_dfs(X,-1);
    reverse(path.begin(),path.end());

    function<void(int,int,int)> dfs_dist = [&](int u,int p,int t){
        for(auto &[v,w]:edge[u]){
            if(v==p) continue;
            dist[v][t]=dist[u][t]+w;
            dfs_dist(v,u,t);
        }
    };
    dfs_dist(X,-1,0);dfs_dist(Y,-1,1);
    long long res=0,sum=0;
    priority_queue<piii,vector<piii>,greater<piii>> pq;
    pq.push({0,{X,0}});pq.push({0,{Y,1}});

    while(!pq.empty()){
        long long d=pq.top().fi;
        int u=pq.top().se.fi,t=pq.top().se.se;pq.pop();
        if(sum+d>K) break;
        sum+=d;res++;cc[u][t]=true;
        for(auto &[v,w]:edge[u]){
            if(!cc[v][t]) pq.push({dist[v][t],{v,t}});
        }
    }

    if(n<=3000){
        priority_queue<long long,vector<long long>,greater<long long>> pq2;
        function<void(int,int)> dfs = [&](int u,int p){
            pq2.push(min(dist[u][0],dist[u][1]));
            for(auto &[v,w]:edge[u]){
                if(v==p || check[v]) continue;
                dfs(v,u);sz[u]+=sz[v];
            }
        };

        int pos=path[0];
        for(int u:path){
            dfs(u,-1);
            for(int i=0;i<=2*n;i++) dp1[u][i]=dp2[u][i]=inf;
            long long d=abs(dist[u][0]-dist[u][1]);
            for(int i=1;i<=sz[u];i++) dp1[u][i]=(i==1?0:dp1[u][i-1])+pq2.top(),pq2.pop();
            for(int i=sz[u];i>=1;i--){
                for(int j=1;j<=i;j++) dp2[u][i+j]=min(dp2[u][i+j],dp1[u][i]+d*j);
            }
            if(dist[u][0]<=dist[u][1]) pos=u;
            /*
            cout << u << '\n';
            for(int i=1;i<=sz[u];i++) cout << dp1[u][i] << ' ';
            cout << '\n';
            for(int i=1;i<=2*sz[u];i++) cout << (dp2[u][i]==inf?-1:dp2[u][i]) << ' ';
            cout << '\n';
            */
        }

        function<void(int,int)> unions2 = [&](int u,int v){
            for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
            for(int i=1;i<=sz[u]+sz[v];i++) nw1[i]=inf;

            for(int i=2*sz[u];i>=1;i--){
                for(int j=1;j<=2*sz[v];j++){
                    nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
                    if(j<=sz[v]){
                        nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp1[v][j]);
                        if(i<=sz[u]) nw1[i+j]=min(nw1[i+j],dp1[u][i]+dp1[v][j]);
                    }
                }
            }
            sz[u]+=sz[v];
            for(int i=1;i<=2*sz[u];i++) dp2[u][i]=nw2[i];
            for(int i=1;i<=sz[u];i++) dp1[u][i]=nw1[i];
        };

        for(int i=0;i<(int)path.size();i++){
            if(i) unions2(path[i],path[i-1]);
            if(path[i]==pos) break;
        }
        //cout << sz[0] << ' ' << sz[1] << '\n';

        for(int t=(int)path.size()-1;t>=0;t--){
            if(path[t]==pos){
                int u=path[t],v=path[t+1];
                for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
                for(int j=1;j<=sz[u];j++) dp2[u][j]=min(dp2[u][j],dp1[u][j]);
                for(int j=1;j<=sz[v];j++) dp2[v][j]=min(dp2[v][j],dp1[v][j]);

                /*
                for(int i=1;i<=2*sz[u];i++) cout << dp2[u][i] << ' ';
                cout << '\n';
                for(int i=1;i<=2*sz[v];i++) cout << dp2[v][i] << ' ';
                cout << '\n';
                */

                for(int i=2*sz[u];i>=1;i--){
                    for(int j=1;j<=2*sz[v];j++) nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
                }
                sz[u]+=sz[v];
                //cout << sz[u] << ' ' << sz[v] << '\n';
                for(long long j=1;j<=2*sz[u];j++){
                    //cout << nw2[j] << ' ';
                    if(nw2[j]<=K) res=max(res,j);
                }
                //cout << '\n';
                break;
            }
            if(t!=(int)path.size()-1)unions2(path[t],path[t+1]);
        }
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17