Submission #201189

#	Time	Username	Problem	Language	Result	Execution time	Memory
201189		extraterrestrial	Meetings (JOI19_meetings)	C++14	100 / 100	696 ms	2744 KiB

meetings

#include "meetings.h"
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
mt19937 rnd(228);

int root, n;

bool cmp(int u, int v) {
	if (u == v) {
		return false;
	}
	return Query(root, u, v) == u;
}

void add(int a, int b) {
	if (a > b) {
		swap(a, b);
	}
	Bridge(a, b);
}

void dfs(int v, vector<int> cur) {
	int u = cur[rnd() % SZ(cur)];
	vector<vector<int>> have(n);
	vector<int> on_path;
	for (int i = 0; i < SZ(cur); i++) {
		int w = cur[i];
		if (w != u) {
			int x = Query(u, v, w);
			if (x == w) {
				on_path.pb(w);
			}
			else {
				have[x].pb(w);
			}
		}
	}
	root = v;
	if (!on_path.empty()) {
		stable_sort(all(on_path), cmp);
		add(v, on_path[0]);
		for (int i = 0; i + 1 < SZ(on_path); i++) {
			add(on_path[i], on_path[i + 1]);
		}
		add(on_path.back(), u);
	}
	else {
		add(u, v);
	}
	if (!have[v].empty()) {
		dfs(v, have[v]);
	}
	if (!have[u].empty()) {
		dfs(u, have[u]);
	}
	for (int x : on_path) {
		if (!have[x].empty()) {
			dfs(x, have[x]);
		}
	}
}

void Solve(int sz) {
	n = sz;
	int root = rnd() % n;
	vector<int> cur;
	for (int i = 0; i < n; i++) {
		if (i != root) {
			cur.pb(i);
		}
	}
	dfs(root, cur);
}

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