Submission #156618

#	Time	Username	Problem	Language	Result	Execution time	Memory
156618		popovicirobert	Meetings (JOI19_meetings)	C++14	29 / 100	3032 ms	928 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;

inline void add(int *special, int x, int &sz) {
	vis[x] = now;
	special[sz++] = x;
}

inline void del(int *special, int x, int &sz) {
	int i, j;
	for(i = 0; i < sz; i++) {
		if(special[i] == x) {
			for(j = i; j + 1 < sz; j++) {
				special[j] = special[j + 1];
			}
			sz--;
			break;

		}
	}
}

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

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

	for(auto it : nodes) {
		dsu.par[it] = -1;
	}

	int special[20], sz = 0;

	for(auto it : nodes) {
		if(vis[it] == now) continue;

		bool ok = 0;
		for(int i = 0; i < sz; i++) {
			int x = special[i];
			//cerr << x << " " << it << " " << root << "\n";
			int cur = Query(x, it, root);
			if(cur == root) continue;

			dsu.join(x, cur);
			dsu.join(it, cur);
			if(x != cur) {
				del(special, x, sz);
				add(special, cur, sz);
			}
			ok = 1;
			break;
		}
		if(ok == 0) {
			add(special, it, sz);
		}
		if(sz > 18) {
			Bridge(0, 0);
		}
	}

	for(int i = 0; i < sz; i++) {
		int cur = special[i];
		//cerr << root << " " << cur << "\n";
		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));

  	vector <int> nodes(n);
	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