제출 #1177172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177172		alexander707070	Closing Time (IOI23_closing)	C++20	8 / 100	181 ms	71088 KiB

closing

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

#define MAXN 1000007
using namespace std;

int n,x,y;
vector< pair<int,int> > v[MAXN];
vector< pair<long long,int> > add[2];

long long dist[MAXN][2];
vector<int> path;
int root[2],vis[MAXN],ban[MAXN];

long long init_cost[2];
vector< pair<long long,int> > costs[2];

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

	for(int i=0;i<2;i++){
		init_cost[i]=0;
		costs[i].clear();
		add[i].clear();
	}

	path.clear();
}

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

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

bool dfs2(int x,int p,int y){
	if(x==y){
		path={y};
		return true;
	}

	for(auto nxt:v[x]){
		if(nxt.first==p)continue;
		if(dfs2(nxt.first,x,y)){
			path.push_back(x);
			return true;
		}
	}

	return false;
}

void greedy(int r){
	long long init=0;
	int start=root[r];
	
	for(int i=1;i<=n;i++)vis[i]=0;

	for(int i:path){
		vis[i]+=1;
		if(i==start)break;
		init+=dist[i][0];
	}

	for(int i=path.size()-1;i>=0;i--){
		vis[path[i]]+=2;
		if(path[i]==start)break;
		init+=dist[path[i]][1];
	}

	init+=max(dist[start][0],dist[start][1]);
	init_cost[r]=init;

	for(int i=1;i<=n;i++){
		if(i==start)continue;
		
		if(vis[i]==0)costs[r].push_back({max(dist[i][0],dist[i][1]),i});
		if(vis[i]==1)costs[r].push_back({dist[i][1]-dist[i][0],i});
		if(vis[i]==2)costs[r].push_back({dist[i][0]-dist[i][1],i});
	}

	sort(costs[r].begin(),costs[r].end());
}

int calc_best(long long s){
	int res=0;
	for(int i=1;i<=n;i++){
		if(ban[i]>0 and ban[i]<3)res++;
		if(ban[i]==3)res+=2;
	}

	int ptl=0,ptr=0;
	while(ptl<n or ptr<n){
		while(ptl<n and ban[add[0][ptl].second]%3==1)ptl++;
		while(ptr<n and ban[add[1][ptr].second]>=2)ptr++;

		if(ptl<n and (ptr==n or add[0][ptl].first<add[1][ptr].first)){
			s-=add[0][ptl].first;
			ptl++;
		}else{
			s-=add[1][ptr].first;
			ptr++;
		}

		if(s<0)break;
		res++;
	}

	return res;
}

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);
	
	sort(add[0].begin(),add[0].end());
	sort(add[1].begin(),add[1].end());

	dfs2(y,0,x);
	for(int i=0;i<path.size()-1;i++){
		if(dist[path[i]][0]<=dist[path[i]][1] and dist[path[i+1]][0]>dist[path[i+1]][1]){
			root[0]=path[i]; root[1]=path[i+1];
			break;
		}
	}

	greedy(0);
	greedy(1);

	int ans=0;
	ans=max(ans,calc_best(K));

	for(int r=0;r<2;r++){

		long long curr=K;
		curr-=init_cost[r];
		if(curr<0)break;
		
		for(int i=1;i<=n;i++)ban[i]=0;

		for(int i:path){
			ban[i]+=1;
			if(i==root[r])break;
		}

		for(int i=path.size()-1;i>=0;i--){
			ban[path[i]]+=2;
			if(path[i]==root[r])break;
		}

		ans=max(ans,calc_best(curr));

		for(int f=0;f<costs[r].size();f++){
			curr-=costs[r][f].first;
			if(curr<0)break;

			ban[costs[r][f].second]=3;
			ans=max(ans,calc_best(curr));
		}
	}

	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";	
	c//out<<max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19})<<"\n";  
	
	return 0;
}*/

• 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