Submission #881791

#	Time	Username	Problem	Language	Result	Execution time	Memory
881791		NK_	Meetings (JOI19_meetings)	C++17	100 / 100	1372 ms	1152 KiB

meetings

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int nax = 2005;

set<int> adj[nax];
int sub[nax], dead[nax];

void gen(int u, int p) {
	sub[u] = 1;
	for(auto& v : adj[u]) if (v != p && !dead[v]) {
		gen(v, u);
		sub[u] += sub[v];
	}
}

int find(int u, int p, int n) {
	for(auto& v : adj[u]) if (v != p && !dead[v]) {
		if (2 * sub[v] > n) return find(v, u, n);
	}

	return u;
}

void rem(int u, int v) {
	adj[u].erase(v);
	adj[v].erase(u);
	// cout << "REM: " << u << " " << v << endl;
}

void add(int u, int v) {
	// cout << "ADD: " << u << " " << v << endl;
	adj[u].insert(v);
	adj[v].insert(u);
}

void place(int x) {
	memset(sub, 0, sizeof sub);
	memset(dead, 0, sizeof sub);

	int r = 0;
	while(1) {
		gen(r, -1);
		// cout << x << " => " << sub[r] << endl;
		int u = find(r, -1, sub[r]);

		vi ADJ; for(auto& v : adj[u]) if (!dead[v]) {
			ADJ.pb(v);
		}

		if (sz(ADJ) == 0) {
			add(u, x);
			return;
		} else if (sz(ADJ) == 1) {
			int v = ADJ[0];
			// cout << "Q1: " << u << " " << v << " " << x << endl;
			int X = Query(u, v, x);
			if (X == u) {
				dead[v] = 1;
				r = u;
			} else if (X == v) {
				dead[u] = 1;
				r = v;
			} else {
				rem(u, v); add(u, X); add(X, v);
				if (X != x) add(X, x);
				return;
			}
		} else {
			for(int i = 0; i < sz(ADJ); i += 2) {

				int a = ADJ[i], b = ADJ[i + 1];

				if (i == sz(ADJ) - 1) {
					r = u;
					break;
				}

				// cout << "Q2: " << a << " " << b << " " << x << endl;
				int R = Query(a, b, x);
				if (R == a || R == b) {
					dead[u] = 1;
					r = R;
					break;
				} else if (R == u) {
					dead[a] = dead[b] = 1;
					r = u;
				} else {
					// In the edge between (a, u) or (b, u)

					// cout << "Q3: " << a << " " << u << " " << x << endl;
					{
						int X = Query(a, u, x);
						if (X != u) {
							// X in between (a, u)
							rem(a, u); add(a, X); add(X, u);
							if (X != x) add(X, x);
							return;
						}
					}

					// cout << "Q3: " << a << " " << u << " " << x << endl;
					{
						int X = Query(b, u, x);
						if (X != u) {
							// x in between (b, u)
							rem(b, u); add(b, X); add(X, u);
							if (X != x) add(X, x);
							return;
						}
					}

					assert(false);
				}
			}
		}
	}

}


void Solve(int N) {
	adj[0] = {1}; adj[1] = {0};

	for(int i = 2; i < N; i++) {
		if (!sz(adj[i])) place(i);

		// for(int x = 0; x < N; x++) for(auto& y : adj[x]) {
		// 	if (x < y) {
		// 		cout << "E: " << x << " " << y << endl;
		// 	}
		// }
		// cout << endl;
	}


	for(int x = 0; x < N; x++) for(auto& y : adj[x]) {
		if (x < y) {
			// cout << "E: " << x << " " << y << endl;
			Bridge(x, y);
		}
	}

}

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