oj.uz

Submission #370992

# Submission time Handle Problem Language Result Execution time Memory
370992 2021-02-25T11:18:45 Z KoD Simurgh (IOI17_simurgh) C++17
51 / 100
 331 ms 4712 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

template <class T>
using Vec = std::vector<T>;

Vec<int> find_roads(int n, Vec<int> U, Vec<int> V) {
	Vec<Vec<std::pair<int, int>>> graph(n);
	const int m = (int) U.size();
	for (int i = 0; i < m; ++i) {
		graph[U[i]].emplace_back(V[i], i);
		graph[V[i]].emplace_back(U[i], i);
	}
	Vec<char> visited(n);
	Vec<int> depth(n), pedge(n, -1);
	Vec<int> edges;
	std::set<int> tree;
	auto dfs = [&](auto dfs, const int u) -> void {
		visited[u] = true;
		for (const auto [v, e]: graph[u]) {
			if (visited[v]) {
				if (depth[u] + 1 < depth[v]) {
					edges.push_back(e);
				}
			}
			else {
				depth[v] = depth[u] + 1;
				pedge[v] = e;
				tree.insert(e);
				dfs(dfs, v);
			}
		}
	};
	dfs(dfs, 0);
	for (int i = 0; i < m; ++i) {
		if (depth[U[i]] > depth[V[i]]) {
			std::swap(U[i], V[i]);
		}
	}
	Vec<char> state(m, 2);
	const auto ask = [&] {
		return count_common_roads(Vec<int>(tree.begin(), tree.end()));
	};
	const auto exchange = [&](const int f, const int e) {
		tree.erase(f);
		tree.insert(e);
		const auto ret = ask();
		tree.insert(f);
		tree.erase(e);
		return ret;
	};	
	const auto base = ask();
	for (const auto e: edges) {
		int X = U[e], Y = V[e];
		Vec<int> ok, ng;
		while (Y != X) {
			const auto f = pedge[Y];
			(state[f] == 2 ? ok : ng).push_back(f);
			Y = U[f];
		}
		Vec<int> same, differ;
		for (const auto f: ok) {
			const auto tmp = exchange(f, e);
			if (tmp < base) {
				state[e] = 0;
				differ.push_back(f);
			}
			else if (tmp > base) {
				state[e] = 1;
				differ.push_back(f);
			}
			else {
				same.push_back(f);
			}
		}
		if (state[e] == 2) {
			if (ng.empty()) {
				state[e] = 0;
			}
			else {
				const auto f = ng.front();
				if (base == exchange(f, e)) {
					state[e] = state[f];
				}
				else {
					state[e] = 1 - state[f];
				}
			}
		}
		for (const auto f: same) {
			state[f] = state[e];
		}
		for (const auto f: differ) {
			state[f] = 1 - state[e];
		}
	}
	Vec<int> ret;
	for (int i = 0; i < m; ++i) {
		if (state[i] != 0) {
			ret.push_back(i);
		}
	}
	return ret;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 364 KB correct
15 Correct 4 ms 364 KB correct
16 Correct 5 ms 364 KB correct
17 Correct 5 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 3 ms 364 KB correct
20 Correct 3 ms 364 KB correct
21 Correct 3 ms 364 KB correct
22 Correct 3 ms 364 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 372 KB correct
32 Correct 2 ms 364 KB correct
33 Correct 2 ms 384 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 364 KB correct
15 Correct 4 ms 364 KB correct
16 Correct 5 ms 364 KB correct
17 Correct 5 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 3 ms 364 KB correct
20 Correct 3 ms 364 KB correct
21 Correct 3 ms 364 KB correct
22 Correct 3 ms 364 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 372 KB correct
32 Correct 2 ms 364 KB correct
33 Correct 2 ms 384 KB correct
34 Correct 313 ms 1772 KB correct
35 Correct 312 ms 1900 KB correct
36 Correct 212 ms 1516 KB correct
37 Correct 14 ms 364 KB correct
38 Correct 325 ms 1772 KB correct
39 Correct 268 ms 1772 KB correct
40 Correct 213 ms 1644 KB correct
41 Correct 331 ms 1872 KB correct
42 Correct 313 ms 1772 KB correct
43 Correct 161 ms 1260 KB correct
44 Correct 128 ms 1132 KB correct
45 Correct 166 ms 1132 KB correct
46 Correct 115 ms 1004 KB correct
47 Correct 52 ms 620 KB correct
48 Correct 4 ms 492 KB correct
49 Correct 14 ms 492 KB correct
50 Correct 49 ms 620 KB correct
51 Correct 150 ms 1140 KB correct
52 Correct 133 ms 1004 KB correct
53 Correct 116 ms 1132 KB correct
54 Correct 161 ms 1260 KB correct
55 Correct 156 ms 1152 KB correct
56 Correct 169 ms 1132 KB correct
57 Correct 155 ms 1132 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Incorrect 243 ms 4712 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 364 KB correct
15 Correct 4 ms 364 KB correct
16 Correct 5 ms 364 KB correct
17 Correct 5 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 3 ms 364 KB correct
20 Correct 3 ms 364 KB correct
21 Correct 3 ms 364 KB correct
22 Correct 3 ms 364 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 372 KB correct
32 Correct 2 ms 364 KB correct
33 Correct 2 ms 384 KB correct
34 Correct 313 ms 1772 KB correct
35 Correct 312 ms 1900 KB correct
36 Correct 212 ms 1516 KB correct
37 Correct 14 ms 364 KB correct
38 Correct 325 ms 1772 KB correct
39 Correct 268 ms 1772 KB correct
40 Correct 213 ms 1644 KB correct
41 Correct 331 ms 1872 KB correct
42 Correct 313 ms 1772 KB correct
43 Correct 161 ms 1260 KB correct
44 Correct 128 ms 1132 KB correct
45 Correct 166 ms 1132 KB correct
46 Correct 115 ms 1004 KB correct
47 Correct 52 ms 620 KB correct
48 Correct 4 ms 492 KB correct
49 Correct 14 ms 492 KB correct
50 Correct 49 ms 620 KB correct
51 Correct 150 ms 1140 KB correct
52 Correct 133 ms 1004 KB correct
53 Correct 116 ms 1132 KB correct
54 Correct 161 ms 1260 KB correct
55 Correct 156 ms 1152 KB correct
56 Correct 169 ms 1132 KB correct
57 Correct 155 ms 1132 KB correct
58 Correct 1 ms 364 KB correct
59 Correct 1 ms 364 KB correct
60 Incorrect 243 ms 4712 KB WA in grader: NO
61 Halted 0 ms 0 KB -