Submission #333686

#	Time	Username	Problem	Language	Result	Execution time	Memory
333686		LucaDantas	Meetings (JOI19_meetings)	C++17	29 / 100	2498 ms	1080 KiB

meetings

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

#define pb push_back
#define sz(a) (a).size()

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count() ^ (long long) (make_unique<char>().get()));

constexpr int maxn = 2e3+10;

vector<int> grp[maxn];

void solve(vector<int> a) {
	if(sz(a) <= 1) return;
	if(sz(a) == 2) return (void)(Bridge(min(a[0], a[1]), max(a[0], a[1])));
	int divide = Query(a[0], a[1], a[2]);
	vector<int> head;
	if(divide == a[0]) head.pb(a[1]);
	else head.pb(a[0]);
	grp[head[0]] = {head[0]};
	for(int x : a) {
		if(x != divide) {
			bool ok = 0;
			for(int y : head) {
				if(x != y) {
					if(Query(divide, x, y) != divide)
						ok = 1, grp[y].pb(x);
				} else ok = 1;
			}
			if(!ok) head.pb(x), grp[x] = {x};
		}
	}
	for(int y : head) {
		int top = y;
		for(int x : grp[y])
			if(x != top)
				top = Query(divide, x, top);
		Bridge(min(divide, top), max(divide, top));
		solve(grp[y]);
	}
}

void Solve(int n) {
	vector<int> a;
	for(int i = 0; i < n; i++)
		a.pb(i);
	shuffle(a.begin(), a.end(), rng);
	solve(a);
}

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