제출 #333703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333703		LucaDantas	Meetings (JOI19_meetings)	C++17	29 / 100	2347 ms	896 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;

void solve(vector<int>& a) {
	shuffle(a.begin(), a.end(), rng);
	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]);
	vector<vector<int>> grp;
	map<int,int> id;
	id[head[0]] = 0;
	grp.pb({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[id[y]].pb(x);
				} else ok = 1;
			}
			if(!ok) id[x] = sz(head), head.pb(x), grp.pb({x});
		}
	}
	for(int y : head) {
		int top = y;
		for(int x : grp[id[y]])
			if(x != top)
				top = Query(divide, x, top);
		Bridge(min(divide, top), max(divide, top));
		solve(grp[id[y]]);
	}
}

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

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