제출 #915447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915447		amirhoseinfar1385	Meetings (JOI19_meetings)	C++17	100 / 100	1268 ms	1388 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10,lg=11;
int n,par[maxn],vis[maxn],visc[maxn],sz[maxn];
vector<int>adj[maxn];
set<int>st[maxn];

void createt(int u){
	for(int i=1;i<=n;i++){
		adj[i].clear();
		visc[i]=0;
		for(auto x:st[i]){
			adj[i].push_back(x);
		}
	}
}

void adde(int u,int v){
	st[u].insert(v);
	st[v].insert(u);
	vis[u]=vis[v]=1;
	return ;
}

void erasee(int u,int v){
	st[u].erase(v);
	st[v].erase(u);
	return ;
}

void calsz(int u,int par=-1){
	sz[u]=1;
	for(auto x:adj[u]){
		if(x!=par&&visc[x]==0){
			calsz(x,u);
			sz[u]+=sz[x];
		}
	}
}

int findc(int u,int mx,int par=-1){
	for(auto x:adj[u]){
		if(x!=par&&visc[x]==0&&sz[x]*2>mx){
			return findc(x,mx,u);
		}
	}
	return u;
}

void solve(int u,int val){
	calsz(u);
	int v=findc(u,sz[u]);
	vector<int>tof;
	for(auto x:adj[v]){
		if(visc[x]==0){
			tof.push_back(x);
		}
	}
	visc[v]=1;
	for(int i=0;i+1<(int)tof.size();i+=2){
		//cout<<"nagoo"<<endl;
		int rr=Query(tof[i]-1,tof[i+1]-1,val-1)+1;
		//cout<<"raft"<<endl;
		if(rr==v){
			continue;
		}
		if(rr==tof[i]){
			solve(tof[i],val);
			return ;
		}
		if(rr==tof[i+1]){
			solve(tof[i+1],val);
			return ;
		}
		val=rr;
		//cout<<"wtf"<<endl;
		rr=Query(tof[i]-1,val-1,v-1)+1;
		//cout<<"raft"<<endl;
		if(rr==val){
			erasee(tof[i],v);
			adde(tof[i],val);
			adde(val,v);
		}
		else{
			erasee(tof[i+1],v);
			adde(tof[i+1],val);
			adde(val,v);
		}
		return ;
	}
	if((int)tof.size()%2==1){
		int rr=Query(val-1,v-1,tof.back()-1)+1;
		if(vis[rr]==0){
			val=rr;
			erasee(tof.back(),v);
			adde(tof.back(),val);
			adde(val,v);
			return ;
		}
		if(rr==tof.back()){
			solve(tof.back(),val);
			return ;
		}
	}
	adde(v,val);
	return ;
}

void in(int u){
	if(u==1){
		vis[u]=1;
		return ;
	}
	if(u==2){
		vis[u]=1;
		par[u]=1;
		adde(1,2);
		return ;
	}
	createt(u);
	solve(1,u);
}

void Solve(int N){
	n=N;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[j]==0){
				in(j);
			}
		}
	}
	int ted=0;
	for(int i=1;i<=n;i++){
		for(auto x:st[i]){
			if(x>i){
				//cout<<x<<" "<<i<<endl;
				ted++;
				Bridge(i-1,x-1);
			}
		}
	}
	if(ted<=1){
		assert(0);
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71