oj.uz

Submission #414616

# Submission time Handle Problem Language Result Execution time Memory
414616 2021-05-30T18:13:07 Z dolphingarlic Simurgh (IOI17_simurgh) C++14
100 / 100
 213 ms 6724 KB 
#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;

int n, m, u[124750], v[124750];
vector<pair<int, int>> graph[500];
int tin[500], low[500], timer = 0, deg[500], cmp[500];
bool visited[500], known[124750], is_golden[124750];
pair<int, int> back_edge[500], par[500];
vector<int> dfs_tree;

void dfs(int node = 0, int parent = -1) {
	visited[node] = true;
	tin[node] = low[node] = timer++;
	for (pair<int, int> i : graph[node]) if (i.first != parent) {
		if (visited[i.first]) {
			low[node] = min(low[node], tin[i.first]);
			if (tin[node] > tin[i.first]) {
				if (back_edge[node].first == -1 || tin[back_edge[node].first] > tin[i.first])
					back_edge[node] = i;
			}
		} else {
			dfs(i.first, node);
			low[node] = min(low[node], low[i.first]);
			if (low[i.first] > tin[node])
				known[i.second] = is_golden[i.second] = true;
			dfs_tree.push_back(i.second);
			par[i.first] = {node, i.second};
		}
	}
}

int find(int A) { return cmp[A] = (A == cmp[A] ? A : find(cmp[A])); }
void onion(int A, int B) { cmp[find(A)] = find(B); }

int query_forest(vector<int> forest) {
	iota(cmp, cmp + n, 0);
	for (int i : forest) onion(u[i], v[i]);
	int delta = 0;
	for (int i : dfs_tree) if (find(u[i]) != find(v[i])) {
		delta -= is_golden[i];
		forest.push_back(i);
		onion(u[i], v[i]);
	}
	return count_common_roads(forest) + delta;
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
	n = _n, m = _u.size();
	for (int i = 0; i < m; i++) {
		u[i] = _u[i], v[i] = _v[i];
		graph[u[i]].push_back({v[i], i});
		graph[v[i]].push_back({u[i], i});
	}
	// First, we find the status of all edges in the DFS tree
	fill_n(back_edge, n, make_pair(-1, -1));
	dfs();
	int dfs_tree_common = count_common_roads(dfs_tree);
	for (int i = 0; i < n; i++) if (~back_edge[i].first) {
		int curr = i;
		bool single_known = false;
		vector<int> unknown;
		while (curr != back_edge[i].first) {
			if (!known[par[curr].second])
				unknown.push_back(par[curr].second);
			else if (!single_known) {
				single_known = true;
				unknown.push_back(par[curr].second);
			}
			curr = par[curr].first;
		}
		if (unknown.size() == 1) continue;
		
		vector<int> query_res;
		for (int j : unknown) {
			vector<int> to_query = {back_edge[i].second};
			for (int k : dfs_tree) if (k != j) to_query.push_back(k);
			query_res.push_back(count_common_roads(to_query));
		}

		int mx = max(dfs_tree_common, *max_element(query_res.begin(), query_res.end()));
		for (int i = 0; i < unknown.size(); i++) {
			known[unknown[i]] = true;
			is_golden[unknown[i]] = (query_res[i] != mx);
		}
	}
	// Next, we get the "degree" of each node in the golden tree
	queue<int> q;
	for (int i = 0; i < n; i++) {
		vector<int> to_query;
		for (pair<int, int> j : graph[i]) to_query.push_back(j.second);
		deg[i] = query_forest(to_query);
		if (deg[i] == 1) q.push(i);
	}
	// Finally, binary search for the "parent" of each node
	while (q.size()) {
		int curr = q.front();
		q.pop();
		if (deg[curr] != 1) continue;
		int l = 0, r = graph[curr].size() - 1;
		while (l != r) {
			int mid = (l + r) / 2;
			vector<int> to_query;
			for (int i = l; i <= mid; i++) to_query.push_back(graph[curr][i].second);
			if (query_forest(to_query)) r = mid;
			else l = mid + 1;
		}
		int nxt, id;
		tie(nxt, id) = graph[curr][l];
		is_golden[id] = true;
		deg[nxt]--;
		if (deg[nxt] == 1) q.push(nxt);
		vector<pair<int, int>> tmp;
		for (pair<int, int> i : graph[nxt]) if (i.second != id) tmp.push_back(i);
		graph[nxt] = tmp;
	}
	// Return the answer
	vector<int> ans;
	for (int i = 0; i < m; i++) if (is_golden[i]) ans.push_back(i);
	return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 0; i < unknown.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 324 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 324 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 2 ms 332 KB correct
15 Correct 3 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 320 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 2 ms 332 KB correct
25 Correct 1 ms 320 KB correct
26 Correct 2 ms 320 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 2 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 2 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 3 ms 332 KB correct
33 Correct 2 ms 316 KB correct
34 Correct 42 ms 1848 KB correct
35 Correct 43 ms 1796 KB correct
36 Correct 34 ms 1484 KB correct
37 Correct 15 ms 452 KB correct
38 Correct 42 ms 1816 KB correct
39 Correct 42 ms 1724 KB correct
40 Correct 38 ms 1520 KB correct
41 Correct 43 ms 1744 KB correct
42 Correct 40 ms 1740 KB correct
43 Correct 33 ms 1228 KB correct
44 Correct 30 ms 972 KB correct
45 Correct 31 ms 1104 KB correct
46 Correct 27 ms 844 KB correct
47 Correct 21 ms 588 KB correct
48 Correct 9 ms 332 KB correct
49 Correct 16 ms 328 KB correct
50 Correct 26 ms 660 KB correct
51 Correct 31 ms 972 KB correct
52 Correct 29 ms 1028 KB correct
53 Correct 29 ms 844 KB correct
54 Correct 33 ms 1228 KB correct
55 Correct 35 ms 1100 KB correct
56 Correct 34 ms 1100 KB correct
57 Correct 33 ms 1116 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 124 ms 4776 KB correct
4 Correct 198 ms 6648 KB correct
5 Correct 183 ms 6564 KB correct
6 Correct 203 ms 6636 KB correct
7 Correct 196 ms 6592 KB correct
8 Correct 213 ms 6532 KB correct
9 Correct 198 ms 6724 KB correct
10 Correct 208 ms 6656 KB correct
11 Correct 199 ms 6684 KB correct
12 Correct 196 ms 6568 KB correct
13 Correct 1 ms 320 KB correct
14 Correct 201 ms 6640 KB correct
15 Correct 207 ms 6656 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 324 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 324 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 2 ms 332 KB correct
15 Correct 3 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 320 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 2 ms 332 KB correct
25 Correct 1 ms 320 KB correct
26 Correct 2 ms 320 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 2 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 2 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 3 ms 332 KB correct
33 Correct 2 ms 316 KB correct
34 Correct 42 ms 1848 KB correct
35 Correct 43 ms 1796 KB correct
36 Correct 34 ms 1484 KB correct
37 Correct 15 ms 452 KB correct
38 Correct 42 ms 1816 KB correct
39 Correct 42 ms 1724 KB correct
40 Correct 38 ms 1520 KB correct
41 Correct 43 ms 1744 KB correct
42 Correct 40 ms 1740 KB correct
43 Correct 33 ms 1228 KB correct
44 Correct 30 ms 972 KB correct
45 Correct 31 ms 1104 KB correct
46 Correct 27 ms 844 KB correct
47 Correct 21 ms 588 KB correct
48 Correct 9 ms 332 KB correct
49 Correct 16 ms 328 KB correct
50 Correct 26 ms 660 KB correct
51 Correct 31 ms 972 KB correct
52 Correct 29 ms 1028 KB correct
53 Correct 29 ms 844 KB correct
54 Correct 33 ms 1228 KB correct
55 Correct 35 ms 1100 KB correct
56 Correct 34 ms 1100 KB correct
57 Correct 33 ms 1116 KB correct
58 Correct 1 ms 332 KB correct
59 Correct 1 ms 332 KB correct
60 Correct 124 ms 4776 KB correct
61 Correct 198 ms 6648 KB correct
62 Correct 183 ms 6564 KB correct
63 Correct 203 ms 6636 KB correct
64 Correct 196 ms 6592 KB correct
65 Correct 213 ms 6532 KB correct
66 Correct 198 ms 6724 KB correct
67 Correct 208 ms 6656 KB correct
68 Correct 199 ms 6684 KB correct
69 Correct 196 ms 6568 KB correct
70 Correct 1 ms 320 KB correct
71 Correct 201 ms 6640 KB correct
72 Correct 207 ms 6656 KB correct
73 Correct 1 ms 332 KB correct
74 Correct 197 ms 6648 KB correct
75 Correct 203 ms 6520 KB correct
76 Correct 108 ms 2740 KB correct
77 Correct 198 ms 6676 KB correct
78 Correct 199 ms 6664 KB correct
79 Correct 201 ms 6724 KB correct
80 Correct 204 ms 6556 KB correct
81 Correct 186 ms 5884 KB correct
82 Correct 206 ms 6544 KB correct
83 Correct 158 ms 3836 KB correct
84 Correct 162 ms 4524 KB correct
85 Correct 153 ms 4244 KB correct
86 Correct 132 ms 2984 KB correct
87 Correct 118 ms 2500 KB correct
88 Correct 116 ms 1752 KB correct
89 Correct 98 ms 1704 KB correct
90 Correct 116 ms 1540 KB correct
91 Correct 55 ms 460 KB correct
92 Correct 34 ms 328 KB correct
93 Correct 157 ms 4304 KB correct
94 Correct 133 ms 2892 KB correct
95 Correct 140 ms 2904 KB correct
96 Correct 111 ms 1624 KB correct
97 Correct 115 ms 1784 KB correct
98 Correct 127 ms 2404 KB correct
99 Correct 117 ms 1768 KB correct
100 Correct 81 ms 716 KB correct
101 Correct 35 ms 332 KB correct
102 Correct 153 ms 3532 KB correct
103 Correct 155 ms 3544 KB correct
104 Correct 153 ms 3576 KB correct
105 Correct 152 ms 3508 KB correct