제출 #201063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201063		extraterrestrial	Meetings (JOI19_meetings)	C++14	29 / 100	2282 ms	16888 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;

int get(int a, int b) {
	if (a > b) {
		swap(a, b);
	}
	return lca[a][b];
}

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;
}

vector<pair<int, int>> edge;

void dfs(int root, vector<int> have) {
	if (have.empty()) {
		return;
	}
	shuffle(all(have), rnd);
	vector<vector<int>> nh(1);
	vector<int> up(1);
	nh[0].pb(have[0]);
	up[0] = have[0];
	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 : order) {
			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]);
					ok = true;
					break;
				}
				else {
					for (auto it : nh[j]) {
						update_lca(it, have[i], v);
						update_lca(it, v, v);
					}
					update_lca(have[i], v, v);
					used[v] = timer;
					up[j] = v;
					nh[j].pb(have[i]);
					if (v != have[i]) {
						nh[j].pb(v);
					}
					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;
  		}
  	}
  }
  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