Submission #156799

#	Time	Username	Problem	Language	Result	Execution time	Memory
156799		popovicirobert	Meetings (JOI19_meetings)	C++14	29 / 100	3022 ms	552 KiB

meetings

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

using namespace std;

static int tot = 0;

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;
static int nodes[MAXN], n;

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(int id) {
	int szn = 0, i;
	for(i = 0; i < n; i++) {
		if(vis[i] == id) {
			nodes[szn++] = i;
			dsu.par[i] = -1;
		}
	}
	if(szn <= 1) return ;
	random_shuffle(nodes, nodes + szn);
	
	int root = nodes[rand() % szn];
	vis[root] = ++now;

	int special[20], sz = 0;

	for(i = 0; i < szn; i++) {
		int it = nodes[i];
		if(vis[it] == now) continue;

		bool ok = 0;
		for(int j = 0; j < sz; j++) {
			int x = special[j];
			//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);
		}
	}

	int bg = now + 1;
	for(i = 0; i < sz; i++) {
		int cur = special[i];
		//cerr << root << " " << cur << "\n";
		Bridge(min(root, cur), max(root, cur));
	}
	for(i = 0; i < szn; i++) {
		if(nodes[i] == root) continue;
		int cur = dsu.root(nodes[i]);
		if(vis[cur] < bg) {
			vis[cur] = ++now;
		}
		vis[nodes[i]] = vis[cur];
	}
	int en = now;
	for(i = bg; i <= en; i++) {
		solve(i);
	}
	
}

void Solve(int N) {
	//double t = clock();
	srand(time(NULL));
	n = N;
	dsu.init(n);
	solve(0);
	//cerr << tot << "\n";
	//cerr << 1.0 * (clock() - t) / CLOCKS_PER_SEC << "\n";
}

Compilation message (stderr)

meetings.cpp:6:12: warning: 'tot' defined but not used [-Wunused-variable]
 static int tot = 0;
            ^~~

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