Submission #1177188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177188		alexander707070	Closing Time (IOI23_closing)	C++20	0 / 100	1101 ms	256020 KiB

closing

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

#define MAXN 1000007
using namespace std;

struct event{
	long long cost;
	int x,type;

	inline friend bool operator < (event fr,event sc){
		return fr.cost>sc.cost;
	}
};

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

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

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

bool reach[MAXN][2];

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

		reach[i][0]=reach[i][1]=false;
	}

	for(int i=0;i<2;i++){
		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]%2==1)ptl++;
		while(ptr<n and ban[add[1][ptr].second]>=2)ptr++;

		if(ptl==n and ptr==n)break;

		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;
}

priority_queue< event > q;

void dfs3(int x,int p,int id,long long d){
	dist[x][id]=d;
	q.push({dist[x][id],x,id});

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

void bfs(int x,int id){
	for(auto nxt:v[x]){
		if(reach[nxt.first][id])continue;

		reach[nxt.first][id]=true;
		if(vis[nxt.first]>0){
			q.push({dist[nxt.first][id] - dist[nxt.first][1-id],nxt.first,id});
		}
	}
}

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);
	sz=int(path.size());
	for(int i=0;i<sz;i++)root[i]=path[i];

	for(int i=0;i<sz;i++)greedy(i);

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

	for(int r=0;r<sz;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));
		}

	}

	reach[x][0]=true;
	reach[y][1]=true;

	while(!q.empty())q.pop();
	dfs3(x,0,0,0);
	dfs3(y,0,1,0);

	for(int i=1;i<=n;i++)vis[i]=0;
	int anss=0;

	while(!q.empty() and K>0){
		event curr=q.top();
		q.pop();

		if(curr.cost>K)break;
		if(vis[curr.x]==3)continue;

		bfs(curr.x,curr.type);

		if(vis[curr.x]>0){
			vis[curr.x]=3;
		}else{
			vis[curr.x]=curr.type+1;
			if(reach[curr.x][1-curr.type])q.push({dist[curr.x][1-curr.type] - curr.cost,1-curr.type});
		}

		K-=curr.cost; anss++;
	}

	return max(ans,anss);
}

/*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: 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