Submission #673488

#	Time	Username	Problem	Language	Result	Execution time	Memory
673488		rainboy	Meetings (JOI19_meetings)	C++17	100 / 100	821 ms	8768 KiB

meetings

#include "meetings.h"
#include <string.h>

const int N = 2000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ej[N][N], eo[N], pp[N], qq[N], sz[N], uu[N], ii[N], jj[N], qu[N], cnt; char used[N];

void append(int i, int j) {
	ej[i][eo[i]++] = j;
}

void remove_(int i, int j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], o++;
			return;
		}
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k)
			if (sz[ii[j]] == sz[i_])
				j++;
			else if (sz[ii[j]] > sz[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void dfs(int p, int i) {
	pp[i] = p, sz[i] = 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			dfs(i, j);
			sz[i] += sz[j];
		}
	}
	sort(ej[i], 0, eo[i]);
	qq[i] = sz[i] == 1 ? -1 : (ej[i][0] == p ? ej[i][1] : ej[i][0]);
	uu[i] = sz[i] == 1 ? i : uu[qq[i]];
}

void up(int i) {
	if (qq[i] != -1)
		up(qq[i]);
	qu[cnt++] = i;
}

void down(int i) {
	qu[cnt++] = i;
	if (qq[i] != -1)
		down(qq[i]);
}

void Solve(int n) {
	for (int i = 0; i < n; i++)
		ii[i] = i;
	for (int j = 0; j < n; j++) {
		int i = rand_() % (j + 1), tmp;
		tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
	}
	memset(eo, 0, n * sizeof *eo);
	memset(used, 0, n * sizeof *used);
	append(ii[0], ii[1]), append(ii[1], ii[0]), used[ii[0]] = used[ii[1]] = 1;
	int r = ii[0];
	for (int i = 2; i < n; i++) {
		int w = ii[i];
		if (used[w])
			continue;
		dfs(-1, r);
		int u = r;
		while (1) {
			int m = 0;
			for (int o = 0; o < eo[u]; o++) {
				int j = ej[u][o];
				if (j != pp[u])
					jj[m++] = j;
			}
			for (int h = u == r ? 0 : 1; h < m; h += 2)
				if (h + 1 < m) {
					int x = Query(uu[jj[h]], uu[jj[h + 1]], w);
					if (x == u)
						continue;
					if (!used[x]) {
						cnt = 0, up(jj[h]), qu[cnt++] = u, down(jj[h + 1]);
						int lower = 0, upper = cnt - 1;
						while (1) {
							int g = (lower + upper) / 2;
							x = Query(qu[g], qu[g + 1], w);
							if (x == qu[g])
								upper = g;
							else if (x == qu[g + 1])
								lower = g + 1;
							else {
								remove_(qu[g], qu[g + 1]), remove_(qu[g + 1], qu[g]);
								append(qu[g], x), append(x, qu[g]);
								append(qu[g + 1], x), append(x, qu[g + 1]);
								if (w != x)
									append(w, x), append(x, w);
								used[w] = used[x] = 1;
								goto out;
							}
						}
					}
					u = x;
					goto nxt;
				} else {
					int x = Query(uu[jj[h]], u, w);
					if (x == u)
						continue;
					if (!used[x]) {
						cnt = 0, up(jj[h]), qu[cnt++] = u;
						int lower = 0, upper = cnt - 1;
						while (1) {
							int g = (lower + upper) / 2;
							x = Query(qu[g], qu[g + 1], w);
							if (x == qu[g])
								upper = g;
							else if (x == qu[g + 1])
								lower = g + 1;
							else {
								remove_(qu[g], qu[g + 1]), remove_(qu[g + 1], qu[g]);
								append(qu[g], x), append(x, qu[g]);
								append(qu[g + 1], x), append(x, qu[g + 1]);
								if (w != x)
									append(w, x), append(x, w);
								used[w] = used[x] = 1;
								goto out;
							}
						}
					}
					u = x;
					goto nxt;
				}
			append(u, w), append(w, u), used[w] = 1;
			break;
nxt:;
		}
out:;
	}
	for (int i = 0; i < n; i++)
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (i < j)
				Bridge(i, j);
		}
}

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