oj.uz

Submission #112268

# Submission time Handle Problem Language Result Execution time Memory
112268 2019-05-18T08:05:06 Z JustInCase Meetings (JOI19_meetings) C++17
100 / 100
 1121 ms 191608 KB 
#include <bits/stdc++.h>
#ifndef skeletaZaPrezident
	#include "meetings.h"
#endif

#define query Query
#define bridge Bridge
#define solve Solve

#define int32_t int
#define int64_t long long

const int32_t MAX_N = 2000;

#ifdef skeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w) {
	std::cout << u << " " << v << " " << w << '\n' << std::flush;

	int32_t res;
	std::cin >> res;

	return res;
}

void bridge(int32_t u, int32_t v) {
	std::cout << "edge: " << u << " " << v << '\n' << std::flush;
}
#endif

#ifndef sekeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w);
void bridge(int32_t u, int32_t v);
#endif

std::map< int32_t, int32_t > asked[MAX_N + 5][MAX_N + 5];

int32_t ask_query(int32_t x, int32_t y, int32_t z) {
	int32_t a[] = { x, y, z };
	std::sort(a, a + 3);

	if(asked[a[0]][a[1]].count(a[2]) == 0) {
		asked[a[0]][a[1]][a[2]] = query(a[0], a[1], a[2]);
	}

	return asked[a[0]][a[1]][a[2]];
}

struct Vertex {
	bool vis;
	int32_t subtreeSize;
	std::vector< int32_t > adjList;

	Vertex() : vis(false), subtreeSize(1) {}
};

bool isInserted[MAX_N + 5];
Vertex t[MAX_N + 5];

bool sort_by_subtree_size(int32_t u, int32_t v) {
	return t[u].subtreeSize > t[v].subtreeSize;
}

void init(int32_t n) {
	for(int32_t i = 0; i < n; i++) {
		t[i].vis = false;
	}
}

void compute_subtree_sizes(int32_t v, int32_t par) {
	t[v].subtreeSize = 1;

	for(auto &x : t[v].adjList) {
		if(x == par || t[x].vis) {
			continue;
		}

		compute_subtree_sizes(x, v);
		t[v].subtreeSize += t[x].subtreeSize;
	}
}

int32_t find_centroid(int32_t v, int32_t par, int32_t target) {
	int32_t maxSubtree = -1, ind = -1;
	for(auto &x : t[v].adjList) {
		if(x == par || t[x].vis) {
			if(t[x].vis) {
				t[x].subtreeSize = 0;
			}

			continue;
		}

		if(t[x].subtreeSize > maxSubtree) {
			maxSubtree = t[x].subtreeSize;
			ind = x;
		}
	}

	if(ind != -1 && maxSubtree > target / 2) {
		return find_centroid(ind, v, target);
	}

	return v;
}

void solve_vertex(int32_t root, int32_t v) {
	compute_subtree_sizes(root, -1);
	int32_t centroid = find_centroid(root, -1, t[root].subtreeSize);
	compute_subtree_sizes(centroid, -1);
	int32_t aux;
	
	std::sort(t[centroid].adjList.begin(), t[centroid].adjList.end(), sort_by_subtree_size);
	for(int32_t i = 0; i < (int32_t) t[centroid].adjList.size(); i++) {
		if(i == (int32_t) t[centroid].adjList.size() - 1) {
			aux = ask_query(centroid, t[centroid].adjList[i], v);

			if(aux == v) {
				t[t[centroid].adjList[i]].adjList.push_back(v);
				t[v].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(v);
				t[v].adjList.push_back(centroid);
				return;
			}

			if(aux == t[centroid].adjList[i]) {
				t[centroid].vis = true;
				solve_vertex(t[centroid].adjList[i], v);
				return;
			}

			if(aux != centroid) {
				solve_vertex(aux, v);
				
				t[t[centroid].adjList[i]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
		
				isInserted[aux] = true;

				return;
			}

			break;
		}

		aux = ask_query(t[centroid].adjList[i], t[centroid].adjList[i + 1], v);

		// v is on the path from t[centroid].adjList[i] to t[centroid].adjList[i + 1]
		if(aux == v) {
			aux = ask_query(t[centroid].adjList[i], centroid, v);

			if(aux == centroid) {
				t[t[centroid].adjList[i + 1]].adjList.push_back(v);
				t[v].adjList.push_back(t[centroid].adjList[i + 1]);

				t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
				
				t[centroid].adjList.push_back(v);
				t[v].adjList.push_back(centroid);
			
				return;
			}
		
			t[t[centroid].adjList[i]].adjList.push_back(v);
			t[v].adjList.push_back(t[centroid].adjList[i]);

			t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
			t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
			
			t[centroid].adjList.push_back(v);
			t[v].adjList.push_back(centroid);

			return;
		}

		if(aux == t[centroid].adjList[i]) {
			t[centroid].vis = true;
			solve_vertex(t[centroid].adjList[i], v);
			return;
		}

		if(aux == t[centroid].adjList[i + 1]) {
			t[centroid].vis = true;
			solve_vertex(t[centroid].adjList[i + 1], v);
			return;
		}

		if(aux != centroid) {
			solve_vertex(aux, v);
			
			int32_t aux2 = ask_query(t[centroid].adjList[i], aux, centroid);
			if(aux2 == centroid) {
				t[t[centroid].adjList[i + 1]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i + 1]);

				t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
			}
			else {
				t[t[centroid].adjList[i]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
			}

			isInserted[aux] = true;
			
			return;
		}
	}

	t[centroid].adjList.push_back(v);
	t[v].adjList.push_back(centroid);
}

void solve(int32_t n) {
	t[0].adjList.push_back(1);
	t[1].adjList.push_back(0);
	
	// solve for each node
	for(int32_t i = 2; i < n; i++) {
		if(isInserted[i]) {
			continue;
		}

		init(n);
		solve_vertex(0, i);	
	}

	for(int32_t i = 0; i < n; i++) {
		for(auto &x : t[i].adjList) {
			if(x > i) {
				bridge(i, x);
			}
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 189224 KB Output is correct
2 Correct 155 ms 189224 KB Output is correct
3 Correct 153 ms 189304 KB Output is correct
4 Correct 157 ms 189236 KB Output is correct
5 Correct 158 ms 189324 KB Output is correct
6 Correct 156 ms 189176 KB Output is correct
7 Correct 162 ms 189224 KB Output is correct
8 Correct 156 ms 189176 KB Output is correct
9 Correct 152 ms 189248 KB Output is correct
10 Correct 152 ms 189204 KB Output is correct
11 Correct 154 ms 189140 KB Output is correct
12 Correct 153 ms 189228 KB Output is correct
13 Correct 154 ms 189260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 189224 KB Output is correct
2 Correct 155 ms 189224 KB Output is correct
3 Correct 153 ms 189304 KB Output is correct
4 Correct 157 ms 189236 KB Output is correct
5 Correct 158 ms 189324 KB Output is correct
6 Correct 156 ms 189176 KB Output is correct
7 Correct 162 ms 189224 KB Output is correct
8 Correct 156 ms 189176 KB Output is correct
9 Correct 152 ms 189248 KB Output is correct
10 Correct 152 ms 189204 KB Output is correct
11 Correct 154 ms 189140 KB Output is correct
12 Correct 153 ms 189228 KB Output is correct
13 Correct 154 ms 189260 KB Output is correct
14 Correct 155 ms 189372 KB Output is correct
15 Correct 157 ms 189176 KB Output is correct
16 Correct 153 ms 189176 KB Output is correct
17 Correct 156 ms 189176 KB Output is correct
18 Correct 159 ms 189352 KB Output is correct
19 Correct 153 ms 189252 KB Output is correct
20 Correct 160 ms 189224 KB Output is correct
21 Correct 154 ms 189160 KB Output is correct
22 Correct 153 ms 189296 KB Output is correct
23 Correct 153 ms 189224 KB Output is correct
24 Correct 162 ms 189276 KB Output is correct
25 Correct 154 ms 189176 KB Output is correct
26 Correct 154 ms 189180 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 189224 KB Output is correct
2 Correct 155 ms 189224 KB Output is correct
3 Correct 153 ms 189304 KB Output is correct
4 Correct 157 ms 189236 KB Output is correct
5 Correct 158 ms 189324 KB Output is correct
6 Correct 156 ms 189176 KB Output is correct
7 Correct 162 ms 189224 KB Output is correct
8 Correct 156 ms 189176 KB Output is correct
9 Correct 152 ms 189248 KB Output is correct
10 Correct 152 ms 189204 KB Output is correct
11 Correct 154 ms 189140 KB Output is correct
12 Correct 153 ms 189228 KB Output is correct
13 Correct 154 ms 189260 KB Output is correct
14 Correct 155 ms 189372 KB Output is correct
15 Correct 157 ms 189176 KB Output is correct
16 Correct 153 ms 189176 KB Output is correct
17 Correct 156 ms 189176 KB Output is correct
18 Correct 159 ms 189352 KB Output is correct
19 Correct 153 ms 189252 KB Output is correct
20 Correct 160 ms 189224 KB Output is correct
21 Correct 154 ms 189160 KB Output is correct
22 Correct 153 ms 189296 KB Output is correct
23 Correct 153 ms 189224 KB Output is correct
24 Correct 162 ms 189276 KB Output is correct
25 Correct 154 ms 189176 KB Output is correct
26 Correct 154 ms 189180 KB Output is correct
27 Correct 162 ms 189408 KB Output is correct
28 Correct 161 ms 189304 KB Output is correct
29 Correct 164 ms 189304 KB Output is correct
30 Correct 159 ms 189468 KB Output is correct
31 Correct 158 ms 189404 KB Output is correct
32 Correct 193 ms 189432 KB Output is correct
33 Correct 168 ms 189476 KB Output is correct
34 Correct 170 ms 189464 KB Output is correct
35 Correct 167 ms 189432 KB Output is correct
36 Correct 168 ms 189432 KB Output is correct
37 Correct 164 ms 189400 KB Output is correct
38 Correct 163 ms 189304 KB Output is correct
39 Correct 163 ms 189372 KB Output is correct

Subtask #4
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 190288 KB Output is correct
2 Correct 830 ms 190328 KB Output is correct
3 Correct 817 ms 190392 KB Output is correct
4 Correct 815 ms 190372 KB Output is correct
5 Correct 593 ms 190288 KB Output is correct
6 Correct 544 ms 190368 KB Output is correct
7 Correct 755 ms 191124 KB Output is correct
8 Correct 877 ms 191352 KB Output is correct
9 Correct 871 ms 191392 KB Output is correct
10 Correct 860 ms 191480 KB Output is correct
11 Correct 947 ms 191500 KB Output is correct
12 Correct 781 ms 190340 KB Output is correct
13 Correct 648 ms 190456 KB Output is correct
14 Correct 822 ms 190820 KB Output is correct
15 Correct 744 ms 191032 KB Output is correct
16 Correct 813 ms 190972 KB Output is correct
17 Correct 898 ms 191600 KB Output is correct
18 Correct 721 ms 190968 KB Output is correct
19 Correct 764 ms 191008 KB Output is correct
20 Correct 810 ms 190932 KB Output is correct
21 Correct 824 ms 190968 KB Output is correct
22 Correct 818 ms 190836 KB Output is correct
23 Correct 830 ms 190952 KB Output is correct
24 Correct 813 ms 190996 KB Output is correct
25 Correct 864 ms 190908 KB Output is correct
26 Correct 830 ms 190968 KB Output is correct
27 Correct 895 ms 190840 KB Output is correct
28 Correct 1065 ms 191480 KB Output is correct
29 Correct 801 ms 191608 KB Output is correct
30 Correct 856 ms 191444 KB Output is correct
31 Correct 895 ms 191372 KB Output is correct
32 Correct 1121 ms 190584 KB Output is correct
33 Correct 874 ms 190780 KB Output is correct
34 Correct 161 ms 189440 KB Output is correct
35 Correct 162 ms 189360 KB Output is correct
36 Correct 160 ms 189388 KB Output is correct
37 Correct 161 ms 189356 KB Output is correct
38 Correct 160 ms 189428 KB Output is correct
39 Correct 159 ms 189352 KB Output is correct
40 Correct 167 ms 189476 KB Output is correct
41 Correct 171 ms 189560 KB Output is correct
42 Correct 171 ms 189500 KB Output is correct
43 Correct 161 ms 189304 KB Output is correct
44 Correct 164 ms 189268 KB Output is correct
45 Correct 165 ms 189408 KB Output is correct
46 Correct 163 ms 189432 KB Output is correct
47 Correct 152 ms 189136 KB Output is correct
48 Correct 153 ms 189304 KB Output is correct
49 Correct 154 ms 189156 KB Output is correct
50 Correct 154 ms 189204 KB Output is correct
51 Correct 153 ms 189176 KB Output is correct
52 Correct 153 ms 189176 KB Output is correct
53 Correct 155 ms 189416 KB Output is correct
54 Correct 152 ms 189304 KB Output is correct
55 Correct 153 ms 189304 KB Output is correct
56 Correct 152 ms 189176 KB Output is correct
57 Correct 153 ms 189348 KB Output is correct
58 Correct 152 ms 189224 KB Output is correct
59 Correct 152 ms 189176 KB Output is correct
60 Correct 152 ms 189112 KB Output is correct
61 Correct 152 ms 189412 KB Output is correct
62 Correct 151 ms 189224 KB Output is correct
63 Correct 153 ms 189176 KB Output is correct
64 Correct 154 ms 189176 KB Output is correct
65 Correct 151 ms 189176 KB Output is correct
66 Correct 151 ms 189296 KB Output is correct
67 Correct 150 ms 189224 KB Output is correct
68 Correct 155 ms 189352 KB Output is correct
69 Correct 154 ms 189304 KB Output is correct
70 Correct 156 ms 189176 KB Output is correct
71 Correct 153 ms 189284 KB Output is correct
72 Correct 154 ms 189320 KB Output is correct