Submission #881791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881791	2023-12-01T23:08:32 Z	NK_	Meetings (JOI19_meetings)	C++17	100 / 100	1372 ms	1152 KB

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.0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	600 KB	Output is correct
4	Correct	344 KB	Output is correct
5	Correct	344 KB	Output is correct
6	Correct	344 KB	Output is correct
7	Correct	344 KB	Output is correct
8	Correct	344 KB	Output is correct
9	Correct	344 KB	Output is correct
10	Correct	344 KB	Output is correct
11	Correct	344 KB	Output is correct
12	Correct	596 KB	Output is correct
13	Correct	600 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	596 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	0 ms	600 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	0 ms	600 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	0 ms	600 KB	Output is correct
20	Correct	0 ms	600 KB	Output is correct
21	Correct	0 ms	600 KB	Output is correct
22	Correct	0 ms	600 KB	Output is correct
23	Correct	0 ms	600 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	600 KB	Output is correct
26	Correct	0 ms	600 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	596 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	0 ms	600 KB	Output is correct
16	Correct	1 ms	756 KB	Output is correct
17	Correct	0 ms	600 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	0 ms	600 KB	Output is correct
20	Correct	0 ms	600 KB	Output is correct
21	Correct	0 ms	600 KB	Output is correct
22	Correct	0 ms	600 KB	Output is correct
23	Correct	0 ms	600 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	600 KB	Output is correct
26	Correct	0 ms	600 KB	Output is correct
27	Correct	5 ms	600 KB	Output is correct
28	Correct	5 ms	636 KB	Output is correct
29	Correct	5 ms	600 KB	Output is correct
30	Correct	5 ms	600 KB	Output is correct
31	Correct	4 ms	600 KB	Output is correct
32	Correct	4 ms	600 KB	Output is correct
33	Correct	5 ms	600 KB	Output is correct
34	Correct	6 ms	600 KB	Output is correct
35	Correct	6 ms	648 KB	Output is correct
36	Correct	4 ms	600 KB	Output is correct
37	Correct	6 ms	600 KB	Output is correct
38	Correct	7 ms	600 KB	Output is correct
39	Correct	6 ms	600 KB	Output is correct

Subtask #4
71.0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	1024 KB	Output is correct
2	Correct	354 ms	848 KB	Output is correct
3	Correct	348 ms	848 KB	Output is correct
4	Correct	411 ms	888 KB	Output is correct
5	Correct	217 ms	916 KB	Output is correct
6	Correct	203 ms	1152 KB	Output is correct
7	Correct	294 ms	848 KB	Output is correct
8	Correct	335 ms	776 KB	Output is correct
9	Correct	310 ms	916 KB	Output is correct
10	Correct	309 ms	800 KB	Output is correct
11	Correct	368 ms	848 KB	Output is correct
12	Correct	344 ms	968 KB	Output is correct
13	Correct	356 ms	812 KB	Output is correct
14	Correct	661 ms	928 KB	Output is correct
15	Correct	635 ms	916 KB	Output is correct
16	Correct	699 ms	788 KB	Output is correct
17	Correct	300 ms	1104 KB	Output is correct
18	Correct	1231 ms	1076 KB	Output is correct
19	Correct	1372 ms	1044 KB	Output is correct
20	Correct	728 ms	928 KB	Output is correct
21	Correct	703 ms	848 KB	Output is correct
22	Correct	720 ms	844 KB	Output is correct
23	Correct	637 ms	1084 KB	Output is correct
24	Correct	683 ms	880 KB	Output is correct
25	Correct	1248 ms	876 KB	Output is correct
26	Correct	1256 ms	912 KB	Output is correct
27	Correct	1262 ms	872 KB	Output is correct
28	Correct	414 ms	1108 KB	Output is correct
29	Correct	296 ms	912 KB	Output is correct
30	Correct	332 ms	900 KB	Output is correct
31	Correct	358 ms	848 KB	Output is correct
32	Correct	481 ms	880 KB	Output is correct
33	Correct	331 ms	1024 KB	Output is correct
34	Correct	5 ms	640 KB	Output is correct
35	Correct	5 ms	600 KB	Output is correct
36	Correct	5 ms	644 KB	Output is correct
37	Correct	5 ms	600 KB	Output is correct
38	Correct	3 ms	584 KB	Output is correct
39	Correct	4 ms	644 KB	Output is correct
40	Correct	5 ms	600 KB	Output is correct
41	Correct	6 ms	600 KB	Output is correct
42	Correct	6 ms	600 KB	Output is correct
43	Correct	4 ms	600 KB	Output is correct
44	Correct	7 ms	600 KB	Output is correct
45	Correct	7 ms	600 KB	Output is correct
46	Correct	6 ms	600 KB	Output is correct
47	Correct	1 ms	600 KB	Output is correct
48	Correct	0 ms	600 KB	Output is correct
49	Correct	1 ms	600 KB	Output is correct
50	Correct	0 ms	600 KB	Output is correct
51	Correct	0 ms	600 KB	Output is correct
52	Correct	0 ms	852 KB	Output is correct
53	Correct	1 ms	600 KB	Output is correct
54	Correct	0 ms	600 KB	Output is correct
55	Correct	1 ms	600 KB	Output is correct
56	Correct	0 ms	600 KB	Output is correct
57	Correct	1 ms	600 KB	Output is correct
58	Correct	0 ms	600 KB	Output is correct
59	Correct	1 ms	600 KB	Output is correct
60	Correct	0 ms	344 KB	Output is correct
61	Correct	0 ms	344 KB	Output is correct
62	Correct	0 ms	600 KB	Output is correct
63	Correct	0 ms	344 KB	Output is correct
64	Correct	0 ms	600 KB	Output is correct
65	Correct	0 ms	344 KB	Output is correct
66	Correct	0 ms	344 KB	Output is correct
67	Correct	0 ms	344 KB	Output is correct
68	Correct	0 ms	344 KB	Output is correct
69	Correct	0 ms	344 KB	Output is correct
70	Correct	0 ms	344 KB	Output is correct
71	Correct	0 ms	344 KB	Output is correct
72	Correct	0 ms	344 KB	Output is correct

Submission #881791

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 10.0 / 10.0

Subtask #3 12.0 / 12.0

Subtask #4 71.0 / 71.0

Subtask #1
7.0 / 7.0

Subtask #2
10.0 / 10.0

Subtask #3
12.0 / 12.0

Subtask #4
71.0 / 71.0