Submission #946931

#	Time	Username	Problem	Language	Result	Execution time	Memory
946931		emptypringlescan	Meetings (JOI19_meetings)	C++17	100 / 100	483 ms	1232 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[2005];
int sz[2005],del[2005];
void dfssize(int x, int p){
	sz[x]=1;
	for(int i:adj[x]){
		if(i==p||del[i]) continue;
		dfssize(i,x);
		sz[x]+=sz[i];
	}
}
int find_cent(int x, int p, int tsz){
	for(int i:adj[x]){
		if(i==p||del[i]) continue;
		if(sz[i]>tsz/2) return find_cent(i,x,tsz);
	}
	return x;
}
bool cmp(int a, int b){
	if(del[a]==0&&del[b]==1) return true;
	else if(del[a]==1&&del[b]==0) return false;
	return sz[a]>sz[b];
}
void Solve(int n){
	mt19937 rng(177013);
	int arr[n];
	for(int i=0; i<n; i++) arr[i]=i;
	shuffle(arr,arr+n,rng);
	adj[arr[0]].push_back(arr[1]);
	adj[arr[1]].push_back(arr[0]);
	for(int i=2; i<n; i++){
		if(!adj[arr[i]].empty()) continue;
		for(int j=0; j<=n; j++) sz[j]=0,del[j]=0;
		int cur=arr[0];
		while(true){
			dfssize(cur,-1);
			cur=find_cent(cur,-1,sz[cur]);
			dfssize(cur,-1);
			sort(adj[cur].begin(),adj[cur].end(),cmp);
			if(adj[cur].empty()||del[adj[cur][0]]){
				adj[cur].push_back(arr[i]);
				adj[arr[i]].push_back(cur);
				break;
			}
			if(adj[cur].size()>=2&&!del[adj[cur][1]]){
				int x=Query(arr[i],adj[cur][0],adj[cur][1]);
				if(x==adj[cur][0]){
					del[cur]=1;
					cur=adj[cur][0];
					continue;
				}
				else if(x==adj[cur][1]){
					del[cur]=1;
					cur=adj[cur][1];
					continue;
				}
				else if(x==cur){
					del[adj[cur][0]]=1;
					del[adj[cur][1]]=1;
					continue;
				}
				else if(x==arr[i]){
					if(Query(arr[i],cur,adj[cur][0])==arr[i]){
						int y=adj[cur][0];
						for(int j=0; j<(int)adj[y].size(); j++){
							if(adj[y][j]==cur){
								adj[y][j]=arr[i];
								break;
							}
						}
						adj[cur][0]=arr[i];
						adj[arr[i]].push_back(cur);
						adj[arr[i]].push_back(y);
					}
					else{
						int y=adj[cur][1];
						for(int j=0; j<(int)adj[y].size(); j++){
							if(adj[y][j]==cur){
								adj[y][j]=arr[i];
								break;
							}
						}
						adj[cur][1]=arr[i];
						adj[arr[i]].push_back(cur);
						adj[arr[i]].push_back(y);
					}
					break;
				}
				else{
					adj[x].push_back(arr[i]);
					adj[arr[i]].push_back(x);
					if(Query(x,cur,adj[cur][0])==x){
						int y=adj[cur][0];
						for(int j=0; j<(int)adj[y].size(); j++){
							if(adj[y][j]==cur){
								adj[y][j]=x;
								break;
							}
						}
						adj[cur][0]=x;
						adj[x].push_back(cur);
						adj[x].push_back(y);
					}
					else{
						int y=adj[cur][1];
						for(int j=0; j<(int)adj[y].size(); j++){
							if(adj[y][j]==cur){
								adj[y][j]=x;
								break;
							}
						}
						adj[cur][1]=x;
						adj[x].push_back(cur);
						adj[x].push_back(y);
					}
					break;
				}
			}
			else{
				int x=Query(arr[i],cur,adj[cur][0]);
				if(x==adj[cur][0]){
					del[cur]=1;
					cur=adj[cur][0];
					continue;
				}
				else if(x==cur){
					adj[cur].push_back(arr[i]);
					adj[arr[i]].push_back(cur);
					break;
				}
				else if(x==arr[i]){
					int y=adj[cur][0];
					for(int j=0; j<(int)adj[y].size(); j++){
						if(adj[y][j]==cur){
							adj[y][j]=arr[i];
							break;
						}
					}
					adj[cur][0]=arr[i];
					adj[arr[i]].push_back(cur);
					adj[arr[i]].push_back(y);
				}
				else{
					adj[x].push_back(arr[i]);
					adj[arr[i]].push_back(x);
					int y=adj[cur][0];
					for(int j=0; j<(int)adj[y].size(); j++){
						if(adj[y][j]==cur){
							adj[y][j]=x;
							break;
						}
					}
					adj[cur][0]=x;
					adj[x].push_back(cur);
					adj[x].push_back(y);
				}
				break;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j:adj[i]){
			if(j>i){
				//cout << i << ' ' << j << '\n';
				Bridge(i,j);
			}
		}
	}
}

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