Submission #156806

#	Time	Username	Problem	Language	Result	Execution time	Memory
156806		popovicirobert	Meetings (JOI19_meetings)	C++14	29 / 100	3102 ms	1344 KiB

meetings

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

using namespace std;

static int tot = 0;



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;

		}
	}
}

static vector <int> g[MAXN];

void dfs(int nod, int id) {
	if(vis[nod] == id) return ;
	vis[nod] = id;
	for(auto it : g[nod]) {
		dfs(it, id);
	}
}

void solve(int id) {
	int szn = 0, i;
	for(i = 0; i < n; i++) {
		if(vis[i] == id) {
			nodes[szn++] = i;
			g[i].clear();
		}
	}
	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;

			g[x].push_back(cur);
			g[cur].push_back(x);
			g[it].push_back(cur);
			g[cur].push_back(it);

			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;	
		dfs(nodes[i], ++now);
	}
	int en = now;
	for(i = bg; i <= en; i++) {
		solve(i);
	}
	
}

void Solve(int N) {
	//double t = clock();
	srand(time(NULL));
	n = 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