Submission #156608

#	Time	Username	Problem	Language	Result	Execution time	Memory
156608		popovicirobert	Meetings (JOI19_meetings)	C++14	29 / 100	3021 ms	992 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

struct DSU {
	vector <int> par;
	int n;

	inline void init(int _n) {
		n = _n;
		par.resize(n, -1);	
	}

	int root(int x) {
		if(par[x] == -1) return x;
		return par[x] = root(par[x]);
	}
	
	inline void join(int x, int y) {
		x = root(x), y = root(y);
		if(x != y) {
			par[x] = y;
		}
	}

}dsu;

const int MAXN = 2000;

static int vis[MAXN], now = 0;


void solve(vector <int> &nodes) {
	if(nodes.empty()) return ;

	int n = nodes.size();
	random_shuffle(nodes.begin(), nodes.end());
	//sort(nodes.rbegin(), nodes.rend());
	int root = nodes[rand() % n];
	now++; vis[root] = now;

	for(auto it : nodes) {
		dsu.par[it] = -1;
		//cerr << it << " ";
	}
	//cerr << "\n";

	set <int> special;
	for(auto it : nodes) {
		if(vis[it] == now || special.find(it) != special.end()) continue;

		bool ok = 0;
		for(auto x : special) {
			//cerr << x << " " << it << " " << root << "\n";
			int cur = Query(x, it, root);
			if(cur == root) continue;

			dsu.join(x, cur);
			dsu.join(it, cur);
			special.erase(x);
			special.insert(cur);
			ok = 1;
			break;
		}

		if(ok == 0) {
			special.insert(it);
		}
	}

	for(auto cur : special) {
		Bridge(min(root, cur), max(root, cur));
		vector <int> aux;
		for(auto it : nodes) {
			if(dsu.root(it) == cur) {
				aux.push_back(it);
			}
		}
		solve(aux);
	}
	
}

void Solve(int n) {
	srand(time(NULL));
	mt19937 rng(time(NULL));

  	vector <int> nodes(n);
	random_shuffle(nodes.begin(), nodes.end());
	iota(nodes.begin(), nodes.end(), 0);
	
	dsu.init(n);
	solve(nodes);
}

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