Submission #1171018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171018		4QT0R	Meetings (JOI19_meetings)	C++17	0 / 100	570 ms	716 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)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 (i==sr)continue;
		possible.clear();
		for (int j = 0; j<i; j++)possible.insert(j);
		possible.insert(sr);

		while(possible.size()>1){
			int v = *possible.begin();
			int u=-1;
			for (int x : graph[v])if (possible.count(x)){
				u=x;
				break;
			}
			int lca=Query(v,u,i);
			if (lca==i){
				odc.erase(correct({v,u}));
				odc.insert(correct({v,i}));
				odc.insert(correct({u,i}));
				graph[v].erase(u);
				graph[u].erase(v);
				graph[v].insert(i);
				graph[u].insert(i);
				graph[i].insert(v);
				graph[i].insert(u);
				break;
			}
			dfs(v^u^lca,lca);
		}
		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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71