Submission #206793

#	Time	Username	Problem	Language	Result	Execution time	Memory
206793		Neklixx	Meetings (JOI19_meetings)	C++14	7 / 100	3077 ms	2604 KiB

meetings

#include <bits/stdc++.h>
#include <meetings.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0);
#define FILE freopen("test.in", "r", stdin);
#define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";}
#define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;}
#define debug cout << "-----------------------------------------------" << endl;
#define print1(a) cout << "{ " << a << " }" << endl;
#define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl;
#define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl;
#define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl;
using namespace std;
//#define int long long
const int INF = 1e9 + 228;
const int MAXN = 3e3 + 28;
int nn = 0;
map<vector<int>, int> ques;
map<pair<int, int>, bool> edges;
bool not_leaf[MAXN];

int ask(int x, int y, int z) {
	vector<int> noww = {x, y, z};
	sort(all(noww));
	if (ques.count(noww) == 0) {
		ques[noww] = Query(x, y, z);
	}
	not_leaf[ques[noww]] = 1;
	return ques[noww];
}

vector<int> g[MAXN];
int p[MAXN];
bool used[MAXN];
int Dsu_get(int x) {
	if (p[x] == x) {
		return x;
	}
	return p[x] = Dsu_get(p[x]);
}

void Dsu_Unique(int x, int y) {
	x = Dsu_get(x);
	y = Dsu_get(y);
	if (x != y)
		p[x] = y;
}

void Solve(int n) {
	nn = n;
	for (int i = 0; i < n; i++) {
		p[i] = i;
	}
	int wonderful = 100000 / (n * n);
	wonderful -= 2;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			vector<int> temp;
			for (int _ = j + 1; _ < n; _++) {
				temp.pb(_);
			}
			random_shuffle(all(temp));
			for (int _ = 0; _ < min((int)temp.size(), wonderful); _++) {
				ask(i, j, temp[_]);
			}
		}
	}
	vector<int> level;
	for (int i = 0; i < n; i++) {
		if (!not_leaf[i])
			level.pb(i);
	}
	while (!level.empty()) {
		vector<int> tmp;	
		sort(all(level));
		level.erase(unique(all(level)), level.end());
		//print1("new_level");	
		for (auto i : level) {
			used[i] = 1;
			//print1(i + 1);
			pair<int, int> res = mp(-1, -1);
			for (int candidate = 0; candidate < n; candidate++) {
				if (candidate == i || Dsu_get(candidate) == Dsu_get(i))
					continue;
				int cnt = 0;
				vector<int> temp;
				for (int j = 0; j < n; j++) {
					if (j == i || j == candidate || Dsu_get(j) == Dsu_get(i))
						continue;
					temp.pb(j);
				}
				random_shuffle(all(temp));
				for (int _ = 0; _ < min((int)temp.size(), wonderful); _++) {
					if (ask(candidate, i, temp[_]) == candidate) {
						cnt++;
					}
				}
				
				res = max(res, mp(cnt, candidate));
			}
			if (res.S == -1)
				continue;
			g[i].pb(res.S);
			g[res.S].pb(i);
			//tmp.pb(res.S);
			//print2(i + 1, res.S + 1);
			Dsu_Unique(i, res.S);
		}
		for (int i = 0; i < n; i++) {
			not_leaf[i] = 0;
		}
		for (int i = 0; i < n; i++) {
			if (used[i])
				continue;
			for (int j = i + 1; j < n; j++) {
				if (used[j])
					continue;
				vector<int> temp;
				for (int _ = j + 1; _ < n; _++) {
					if (used[_])
						continue;
					temp.pb(_);
				}
				random_shuffle(all(temp));
				for (int _ = 0; _ < min((int)temp.size(), wonderful); _++) {
					ask(i, j, temp[_]);
				}
			}
		}
		level.clear();
		for (int i = 0; i < n; i++) {
			if (!used[i] && !not_leaf[i])
				level.pb(i);
		}
	}
	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			if (!edges[mp(i, to)] && !edges[mp(to, i)]) {
				edges[mp(i, to)] = edges[mp(to, i)] = 1;
				Bridge(i, to);
			}
		}
	}
}

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