Submission #242644

#	Time	Username	Problem	Language	Result	Execution time	Memory
242644		ZwariowanyMarcin	Meetings (JOI19_meetings)	C++14	100 / 100	1020 ms	1052 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int N = 2100;
/*
int Query(int x, int y, int z) {
	printf ("ask %d %d %d\n", x, y, z);
	int d;
	cin >> d;
	return d;
}

void Bridge(int x, int y) {
	printf ("tree %d %d\n", x, y);
}*/

void bridge(int x, int y) {
	if (x > y) swap(x, y);
	Bridge(x, y);
}

vector <int> g[N];

void rek(vector <int> x, int root) {
	if (ss(x) == 1) return;
	int y = x[rand() % ss(x)];
	while (y == root)
		y = x[rand() % ss(x)];
	for (auto it : x)
		g[it].clear();
	vector <int> path;
	for (auto it : x) {
		if (it == y || it == root) continue;
		int z = Query(root, y, it);
		if (it == z) path.pb(it);
		g[z].pb(it);
	}
	g[root].pb(root);
	g[y].pb(y);
	sort(all(path), [&](int a, int b) {
		int c = Query(root, a, b);
		if (c == a) return 1;
		else return 0;
	});
	// 1. 
	int First = (path.empty() ? y : path[0]);
	bridge(First, root);
	rep(i, 0, ss(path) - 1) 
		bridge(path[i], (i + 1 < ss(path) ? path[i + 1] : y));
	for (auto it : x)
		if (!g[it].empty())
			rek(g[it], it);
}
	

void Solve(int n) {
	srand(2137);
	vector <int> v(n);
	iota(all(v), 0);
	int root = rand() % n;
	rek(v, root);
}

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