Submission #470454

#	Time	Username	Problem	Language	Result	Execution time	Memory
470454		Namnamseo	Meetings (JOI19_meetings)	C++17	0 / 100	71 ms	496 KiB

meetings

#include "meetings.h"
#include <algorithm>
#include <map>
#include <numeric>
#include <vector>
using namespace std;

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

void work_set(vector<int> &v) {
	if (v.size() == 1u) return;
	int a = v[0], b = v[1], n = v.size();
	map<int, vector<int>> roots; roots[a]; roots[b];
	for (int i=2; i<n; ++i) roots[Query(a, b, v[i])].push_back(v[i]);
	for (auto &tmp : roots) {
		if (tmp.first == a || tmp.first == b) tmp.second.push_back(tmp.first);
		work_set(tmp.second);
	}
	n = roots.size()-2u;
	vector<int> foots; foots.reserve(n);
	for (auto &tmp : roots) if (tmp.first != a && tmp.first != b) foots.push_back(tmp.first);
	if (foots.empty()) { bridge(a, b); return; }
	roots = move(decltype(roots)());
	sort(foots.begin(), foots.end(), [&](const int& x, const int& y) {
		return Query(x, y, a) == a;
	});
	bridge(a, foots[0]);
	for (int i=1; i<n; ++i) bridge(foots[i-1], foots[i]);
	bridge(foots[n-1], b);
}

void Solve(int N) {
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	work_set(v);
}

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