Submission #840164

#	Time	Username	Problem	Language	Result	Execution time	Memory
840164		KLPP	Closing Time (IOI23_closing)	C++17	75 / 100	1104 ms	674504 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#include <vector>
int n;
lld pref[1000000];
lld distX[1000000];
lld distY[1000000];
vector<pair<int,lld> >nei[1000000];
void DFSX(int node, lld dist=0){
	distX[node]=dist;
	trav(a,nei[node]){
		if(distX[a.first]==-1){
			DFSX(a.first,dist+a.second);
		}
	}
}
void DFSY(int node, lld dist=0){
	distY[node]=dist;
	trav(a,nei[node]){
		if(distY[a.first]==-1){
			DFSY(a.first,dist+a.second);
		}
	}
}
vector<lld> diffs;
vector<lld> dists[1000000];
vector<lld >gains[1000000];
vector<lld >gainsX[1000000];
vector<lld >gainsY[1000000];
lld absol(lld x){
	return max(x,-x);
}
vector<lld> DP[1000000][3];

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	n=N;
	rep(i,0,n)nei[i].clear(),distX[i]=-1,distY[i]=-1;
	rep(i,0,n-1){
		nei[U[i]].push_back({V[i],W[i]});
		nei[V[i]].push_back({U[i],W[i]});
	}
	DFSX(X);
	DFSY(Y);
	priority_queue<lld> pq;
	rep(i,0,n){
		pq.push(-distX[i]);
		pq.push(-distY[i]);
	}
	lld sum=0;
	int cnt=0;
	while(!pq.empty() && sum<=K){
		lld d=-pq.top();
		pq.pop();
		sum+=d;
		cnt++;
	}
	if(sum>K)cnt--;
	int ans=cnt;
	diffs.clear();
	rep(i,0,n)diffs.push_back(distX[i]-distY[i]);
	sort(diffs.begin(),diffs.end());
	diffs.resize(unique(diffs.begin(),diffs.end())-diffs.begin());
	int m=diffs.size();
	rep(i,0,m)gains[i].clear(),dists[i].clear(),gainsX[i].clear(),gainsY[i].clear();
	rep(i,0,n){
		int pos=lower_bound(diffs.begin(),diffs.end(),distX[i]-distY[i])-diffs.begin();
		dists[pos].push_back(min(distX[i],distY[i]));
	}
	rep(i,0,m)sort(dists[i].begin(),dists[i].end());
	rep(i,0,m){
		lld delta=absol(diffs[i]);
		int cnt=0;
		gains[i].push_back(0);
		gains[i].push_back(delta);
		gains[i].push_back(dists[i][0]);
		rep(j,1,(int)dists[i].size()){
			lld a=dists[i][j];
			if(a<delta){
				gains[i].push_back(a);
				cnt++;
			}else{
				while(cnt>0){
					gains[i].push_back(delta);
					cnt--;
				}
				gains[i].push_back(a);
				cnt++;
			}
		}
		while(cnt>0){
			gains[i].push_back(delta);
			cnt--;
		}
		
		rep(j,0,(int)gains[i].size()-1)gains[i][j+1]+=gains[i][j];
		gains[i][0]=1e18;
		gains[i][1]=1e18;

		gainsX[i].push_back(0);
		trav(a,dists[i]){
			gainsX[i].push_back(a);
		}
		gainsY[i].push_back(0);
		trav(a,dists[i])gainsY[i].push_back(a+delta);
		rep(j,0,(int)gainsX[i].size()-1)gainsX[i][j+1]+=gainsX[i][j];
		rep(j,0,(int)gainsY[i].size()-1)gainsY[i][j+1]+=gainsY[i][j];
		gainsX[i][0]=1e18;
		gainsY[i][0]=1e18;
		if(diffs[i]>0)swap(gainsX[i],gainsY[i]);
		
	}
	rep(i,0,m+1){
		rep(j,0,3)DP[i][j].clear();
	}
	DP[0][0].resize(2*n+1,1e18);
	DP[0][1].resize(2*n+1,1e18);
	DP[0][2].resize(2*n+1,1e18);
	DP[0][0][0]=0;
	DP[0][1][0]=0;
	DP[0][2][0]=0;
	rep(i,0,m){
		rep(j,0,3){
			DP[i+1][j].resize(2*n+1,1e18);
		}
		rep(l,0,3){
			rep(j,l,3){
				rep(k,0,2*n+1){
					if(j==0){
						rep(o,0,(int)gainsX[i].size()){
							if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gainsX[i][o]);
						}
					}
					if(j==1){
						rep(o,0,(int)gains[i].size()){
							if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gains[i][o]);
						}
					}
					if(j==2){
						rep(o,0,(int)gainsY[i].size()){
							if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gainsY[i][o]);
						}
					}
				}
			}
		}
	}
	rep(i,0,2*n+1){
		//cout<<DP[m][2][i]<<" ";
		rep(j,0,3){
			if(DP[m][j][i]<=K)ans=max(ans,i);
		}
	}
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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: 10 / 10
• Subtask 9: 0 / 17