Submission #201067

#	Time	Username	Problem	Language	Result	Execution time	Memory
201067		extraterrestrial	Meetings (JOI19_meetings)	C++14	29 / 100	3068 ms	17668 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
mt19937 rnd(228);

const int N = 2010;
int lca[N][N], used[N], timer;
bitset<N> dk[N], em, cur[18], kek;
inline int get(int a, int b) {
	if (a > b) {
		swap(a, b);
	}
	return lca[a][b];
}

inline void update_lca(int a, int b, int c) {
	if (a > b) {
		swap(a, b);
	}
	if (lca[a][b] != -1) {
		assert(lca[a][b] == c);
	}
	lca[a][b] = c;
	dk[a][b] = dk[b][a] = 0;
}

vector<pair<int, int>> edge;

void dfs(int root, vector<int> &have) {
	if (have.empty()) {
		return;
	}
	for (int i = 0; i < 18; i++) {
		cur[i] = em;
	}
	//shuffle(all(have), rnd);
	vector<vector<int>> nh(1);
	vector<int> up(1);
	nh[0].pb(have[0]);
	up[0] = have[0];
	cur[0][have[0]] = 1;
	timer++;
	used[have[0]] = timer;
	for (int i = 1; i < SZ(have); i++) {
		if (used[have[i]] == timer) {
			continue;
		}
		used[have[i]] = timer;
		bool ok = false;
		vector<int> order;
		/*for (int j = 0; j < SZ(nh); j++) {
			order.pb(j);
		}
		shuffle(all(order), rnd);*/
		for (int j = 0; j < SZ(nh); j++) {
			if (ok) {
				break;
			}
			int v;
			if (get(up[j], have[i]) != -1) {
				v = get(up[j], have[i]);
			}
			else {
				v = Query(root, up[j], have[i]);
			}
			if (v != root) {
				if (v == up[j]) {
					update_lca(v, up[j], up[j]);
					nh[j].pb(have[i]);
					cur[j][have[i]] = 1;
					ok = true;
					break;
				}
				else {
					/*kek = dk[have[i]] & cur[j];
					int cnt = kek.count();
					for (int iter = 0; iter < cnt; iter++) {
						int pos = kek._Find_first();
						kek[pos] = 0;
						update_lca(pos, have[i], v);
					}
					kek = dk[v] & cur[j];
					cnt = kek.count();
					for (int iter = 0; iter < cnt; iter++) {
						int pos = kek._Find_first();
						kek[pos] = 0;
						update_lca(pos, v, v);
					}*/
					update_lca(have[i], v, v);
					used[v] = timer;
					up[j] = v;
					nh[j].pb(have[i]);
					cur[j][have[i]] = 1;
					if (v != have[i]) {
						nh[j].pb(v);
						cur[j][v] = 1;
					}
					ok = true;
					break;
				}
			}
		}
		if (!ok) {
			nh.pb({have[i]});
			up.pb(have[i]);
		}
	}
	for (auto it : up) {
		edge.pb({root, it});
	}
	for (int i = 0; i < SZ(nh); i++) {
		for (int j = 0; j < SZ(nh[i]); j++) {
			if (nh[i][j] == up[i]) {
				nh[i].erase(nh[i].begin() + j);
				break;
			}
		}
		dfs(up[i], nh[i]);
	}
}

void Solve(int n) {
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < n; j++) {
  		if (i == j) {
  			lca[i][j] = i;
  		}
  		else {
  			lca[i][j] = -1;
  			dk[i][j] = dk[j][i] = 1;
  		}
  	}
  }
  int root = rnd() % n;
  vector<int> have;
  for (int i = 0; i < n; i++) {
  	if (i != root) {
  		have.pb(i);
  	}
  }
  dfs(root, have);
  for (auto &it : edge) {
  	if (it.F > it.S) {
  		swap(it.F, it.S);
  	}
  	Bridge(it.F, it.S);
  }
}

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