Submission #1177644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177644		alexander707070	Closing Time (IOI23_closing)	C++20	75 / 100	1094 ms	343300 KiB

closing

#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

const long long inf=1000000000000000007;

int n,x,y,sz[2*MAXN],num,ans;
vector< pair<int,int> > v[MAXN];
vector<int> w[2*MAXN];
int path[MAXN],szp,pref[MAXN];

long long dist[MAXN][2];
bool special[MAXN];

long long dp[2*MAXN][2*MAXN][3];
long long dp2[MAXN][2*MAXN][3];

void reset(){
	for(int i=1;i<=n;i++){
		special[i]=false;
		v[i].clear();
	}

	szp=0; ans=0;
	for(int i=1;i<=2*n;i++){
		w[i].clear(); sz[i]=0;
	}
}

int greedy(long long K){
	vector<long long> vals;
	for(int i=1;i<=n;i++){
		vals.push_back(dist[i][0]);
		vals.push_back(dist[i][1]);
	}

	sort(vals.begin(),vals.end());

	int res=0;
	for(int i=0;i<vals.size();i++){
		K-=vals[i];
		if(K<0)break;
		res++;
	}

	return res;
}

void dfs(int x,int p,int id,long long d){
	dist[x][id]=d;

	for(auto nxt:v[x]){
		if(nxt.first==p)continue;
		dfs(nxt.first,x,id,d+nxt.second);
	}
}

bool findv(int x,int p,int y){
	if(x==y){
		special[y]=true;
		szp++; path[szp]=y;
		return true;
	}

	for(auto nxt:v[x]){
		if(nxt.first==p)continue;

		if(findv(nxt.first,x,y)){
			special[x]=true;
			szp++; path[szp]=x;
			return true;
		}
	}

	return false;
}

void build(int x,int p){

	vector<int> c;
	for(auto nxt:v[x]){
		if(nxt.first==p or special[nxt.first])continue;
		build(nxt.first,x);

		c.push_back(nxt.first);
	}

	if(c.empty())return;
	if(c.size()==1){
		w[x].push_back(c[0]);
		return;
	}

	int curr=c[0];
	for(int i=1;i<int(c.size())-1;i++){
		num++;
		w[num].push_back(curr);
		w[num].push_back(c[i]);
		curr=num;
	}

	w[x].push_back(curr);
	w[x].push_back(c.back());
}

void dfs2(int x){
	sz[x]=(x<=n);

	for(auto nxt:w[x]){
		dfs2(nxt);
		sz[x]+=sz[nxt];
	}
}

long long cost(int x,int s){
	if(s==0)return dist[x][0];
	if(s==1)return dist[x][1];
	return max(dist[x][0],dist[x][1]);
}

void calcdp(int x){
	for(auto nxt:w[x]){
		calcdp(nxt);
	}

	for(int ver=0;ver<3;ver++){
		for(int k=0;k<=2*sz[x];k++){

			if((ver<2 and k>sz[x])){
				dp[x][k][ver]=inf;
				continue;
			}

			dp[x][k][ver]=inf;
			if(ver==2 and !special[x]){
				dp[x][k][ver]=min(dp[x][k][0],dp[x][k][1]);
			}

			if(k==0){
				dp[x][k][ver]=0;
				continue;
			}

			int coef=ver/2+1;

			if(x>n){
				for(int s=k-coef*sz[w[x][1]];s<=coef*sz[w[x][0]];s++){
					
					if(s<0)continue;
					if(k-s<0)continue;

					dp[x][k][ver]=min(dp[x][k][ver] , dp[w[x][0]][s][ver] + dp[w[x][1]][k-s][ver] );
				}
			}else{
				int red=ver/2+1;

				if(w[x].empty()){
					dp[x][k][ver]=min(dp[x][k][ver],cost(x,ver));
				}else if(w[x].size()==1){

					if(k-red<=0)dp[x][k][ver]=min(dp[x][k][ver],cost(x,ver));
					else dp[x][k][ver]=min(dp[x][k][ver],dp[w[x][0]][k-red][ver] + cost(x,ver));
				}else{

					for(int s=k-red-coef*sz[w[x][1]];s<=coef*sz[w[x][0]];s++){
					
						if(s<0)continue;
						if(k-red-s<0)continue;
	
						dp[x][k][ver]=min(dp[x][k][ver] , dp[w[x][0]][s][ver] + dp[w[x][1]][k-red-s][ver] + cost(x,ver) );
					}
				}
			}
		}
	}
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
	n=N; x=X+1; y=Y+1;

	reset();

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

	dfs(x,0,0,0);
	dfs(y,0,1,0);

	findv(x,0,y);
	reverse(path+1,path+szp+1);

	num=n;
	for(int i=1;i<=n;i++){
		if(special[i]){
			build(i,0);
			dfs2(i);
			calcdp(i);
		}
	}
	
	for(int k=1;k<=2*n;k++){
		dp2[0][k][0]=dp2[0][k][1]=dp2[0][k][2]=inf;
	}

	for(int i=1;i<=szp;i++){
		pref[i]=pref[i-1]+sz[path[i]];
	}

	for(int i=1;i<=szp;i++){
		for(int k=i;k<=2*n;k++){
			for(int state=0;state<=2;state++){
				
				dp2[i][k][state]=inf;
				if(state>0)dp2[i][k][state]=dp2[i][k][state-1];

				int coef=1;
				if(state==1)coef=2;

				int ver=3-state;
				if(ver==3)ver=0;

				int ptr=2;
				if(state==0)ptr=1;

				for(int t=max(1,k-pref[i-1]*ptr);k-t>=i-1 and t<=coef*sz[path[i]];t++){
					dp2[i][k][state]=min(dp2[i][k][state],dp[path[i]][t][ver] + dp2[i-1][k-t][state]);			
				}
			}
		}
	}

	for(int i=2*n;i>=szp;i--){
		if(dp2[szp][i][2]<=K){
			ans=i; break;
		}
	}

	ans=max(ans,greedy(K));

	return ans;
}

/*int main(){

	cout<<max_score(7, 0, 2, 10,
		{0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3})<<"\n";

		cout<<max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19})<<"\n";

	return 0;
}*/

• 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