Submission #1171087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171087		4QT0R	Meetings (JOI19_meetings)	C++17	29 / 100	1353 ms	1112 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;
}

void Solve(int N){
	set<pair<int,int>> odc;
	siz.resize(N+1);
	int sr=Query(0,1,2);
	for (int i = 0; i<3; i++){
		if (sr!=i){
			graph[sr].insert(i);
			graph[i].insert(sr);
			odc.insert(correct({sr,i}));
		}
	}
	for (int i = 3; i<N; i++){
		if (graph[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,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 (i!=lca){
					graph[i].insert(lca);
					graph[lca].insert(i);
					odc.insert(correct({lca,i}));
				}
				break;
			}
		}
		if (graph[i].size())continue;
		int v = *possible.begin();
		graph[v].insert(i);
		graph[i].insert(v);
		odc.insert(correct({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