Submission #1171093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171093		4QT0R	Meetings (JOI19_meetings)	C++17	29 / 100	1398 ms	1120 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

pair<int,int> correct(pair<int,int> p){
	if (p.first>p.second)swap(p.first,p.second);
	return p;
}

set<int> graph[2002];
set<int> possible;
vector<int> siz;

void dfs(int v, int p){
	possible.erase(v);
	for (auto u : graph[v]){
		if (u==p || !possible.count(u))continue;
		dfs(u,v);
	}
}

pair<int,int> find_mid(int v, int p){
	siz[v]=1;
	pair<int,int> cur={-1,-1};
	for (auto u : graph[v]){
		if (u==p || !possible.count(u))continue;
		pair<int,int> tmp=find_mid(u,v);
		if (tmp.first!=-1)return tmp;
		if (cur.second==-1 || siz[u]>siz[cur.second])cur.second=u;
		siz[v]+=siz[u];
	}
	if (2*siz[v]>=(int)possible.size()){
		cur.first=v;
		if (cur.second==-1 || (siz[cur.second]+siz[v]<(int)possible.size() && p!=-1))cur.second=p;
	}
	return cur;
}

mt19937 losowe(chrono::high_resolution_clock::now().time_since_epoch().count());

void Solve(int N){
	set<pair<int,int>> odc;
	siz.resize(N+1);
	int x=losowe()%N,y=losowe()%N,z=losowe()%N;
	while(y==x)y=losowe()%N;
	while(z==x || z==y)z=losowe()%N;

	int sr=Query(x,y,z);
	if (sr!=x){
		graph[sr].insert(x);
		graph[x].insert(sr);
		odc.insert(correct({sr,x}));
	}
	if (sr!=y){
		graph[sr].insert(y);
		graph[y].insert(sr);
		odc.insert(correct({sr,y}));
	}
	if (sr!=z){
		graph[sr].insert(z);
		graph[z].insert(sr);
		odc.insert(correct({sr,z}));
	}
	vector<int> kol(N);
	for (int i = 0; i<N; i++)kol[i]=i;
	shuffle(kol.begin(),kol.end(),losowe);
	for (int i = 0; i<N; i++){
		if (graph[kol[i]].size())continue;
		possible.clear();
		for (int j = 0; j<N; j++)if (graph[j].size())possible.insert(j);

		while(possible.size()>1){
			pair<int,int> st = find_mid(*possible.begin(),-1);
			int v=st.first;
			int u=st.second;
			int lca=Query(v,u,kol[i]);
			if (lca==v)dfs(u,v);
			else if (lca==u)dfs(v,u);
			else{
				odc.erase(correct({v,u}));
				odc.insert(correct({v,lca}));
				odc.insert(correct({u,lca}));
				graph[v].erase(u);
				graph[u].erase(v);
				graph[v].insert(lca);
				graph[u].insert(lca);
				graph[lca].insert(v);
				graph[lca].insert(u);
				if (kol[i]!=lca){
					graph[kol[i]].insert(lca);
					graph[lca].insert(kol[i]);
					odc.insert(correct({lca,kol[i]}));
				}
				break;
			}
		}
		if (graph[kol[i]].size())continue;
		int v = *possible.begin();
		graph[v].insert(kol[i]);
		graph[kol[i]].insert(v);
		odc.insert(correct({kol[i],v}));
	}
	for (auto e : odc)Bridge(e.first,e.second);
}

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