Submission #1171053

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

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

void Solve(int N){
	set<pair<int,int>> odc;
	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){
			int v = *possible.begin();
			int u=-1;
			for (int x : graph[v])if (possible.find(x)!=possible.end()){
				u=x;
				break;
			}
			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