Submission #759411

#	Time	Username	Problem	Language	Result	Execution time	Memory
759411		ymm	Meetings (JOI19_meetings)	C++17	100 / 100	606 ms	1148 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

int query(int i, int j, int k) {
	if (i == j || i == k)
		return i;
	if (j == k)
		return j;
	return Query(i, j, k);
}

mt19937_64 rd(time(0));

void solve(vector<int> vec)
{
	shuffle(vec.begin(), vec.end(), rd);
	int rt = query(vec[rd()%vec.size()], vec[rd()%vec.size()], vec[rd()%vec.size()]);
	struct dard { vector<int> vec; int rt; };
	vector<dard> marg;
	set<int> done = {rt};
	for (int v : vec) {
		if (done.count(v))
			continue;
		done.insert(v);
		bool found = 0;
		Loop (i,0,marg.size()) {
			int x = query(rt, marg[i].rt, v);
			if (x == rt)
				continue;
			marg[i].rt = x;
			marg[i].vec.push_back(v);
			if (done.insert(x).second)
				marg[i].vec.push_back(x);
			for (int j = i; j > 0; --j) {
				if (marg[j-1].vec.size() >= marg[j].vec.size())
					break;
				marg[j-1].vec.swap(marg[j].vec);
				swap(marg[j-1].rt, marg[j].rt);
			}
			found = 1;
			break;
		}
		if (!found)
			marg.push_back({{v}, v});
	}
	Loop (i,0,marg.size())
		Bridge(min(rt, marg[i].rt), max(rt, marg[i].rt));
	Loop (i,0,marg.size())
		solve(marg[i].vec);
}


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

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