oj.uz

Submission #51898

# Submission time Handle Problem Language Result Execution time Memory
51898 2018-06-22T13:45:41 Z aome Simurgh (IOI17_simurgh) C++17
51 / 100
 182 ms 7912 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

const int N = 510;
const int M = 510 * 510 / 2;

int n, m;
int h[N];
pair<int, int> par[N];
bool visit[N];
bool tree_edge[M];
int visit_edge[M];
pair<int, int> e[M];
vector< pair<int, int> > G[N];

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (visit[v.first]) continue;
		tree_edge[v.second] = 1, h[v.first] = h[u] + 1;
		par[v.first] = {u, v.second}, dfs(v.first);  
	}
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
	n = _n, m = _u.size();
	for (int i = 0; i < m; ++i) {
		e[i] = {_u[i], _v[i]};
		G[_u[i]].push_back({_v[i], i});
		G[_v[i]].push_back({_u[i], i});
	}
	dfs(0);
	vector<int> vec;
	for (int i = 0; i < m; ++i) {
		if (tree_edge[i]) vec.push_back(i);
	}
	int val = count_common_roads(vec);
	for (int i = 0; i < m; ++i) {
		if (h[e[i].first] > h[e[i].second]) swap(e[i].first, e[i].second);
		if (tree_edge[i]) continue;
		int cur = e[i].second;
		vector<int> buf;
		while (cur != e[i].first) {
			buf.push_back(par[cur].second), cur = par[cur].first;
		}
		int id = -1;
		for (auto j : buf) {
			if (visit_edge[j]) id = j;
		}
		if (id == -1) {
			for (auto j : buf) {
				vector<int> ask = vec;
				for (auto &k : ask) if (k == j) k = i;
				int tmp = count_common_roads(ask);
				if (tmp != val) {
					visit_edge[i] = (tmp > val) + 1;
					visit_edge[j] = 3 ^ visit_edge[i];
					// 1 : not loyal, 2 : loyal
				}
			}
			if (!visit_edge[i]) visit_edge[i] = 1;
			for (auto j : buf) {
				if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
			}
		}
		else {
			vector<int> ask = vec;
			for (auto &j : ask) if (j == id) j = i;
			int tmp = count_common_roads(ask);
			if (tmp == val) visit_edge[i] = visit_edge[id];
			else visit_edge[i] = 3 ^ visit_edge[id];
			for (auto j : buf) {
				if (!visit_edge[j]) {
					vector<int> ask = vec;
					for (auto &k : ask) if (k == j) k = i;
					int tmp = count_common_roads(ask);
					if (tmp == val) visit_edge[j] = visit_edge[i];
					else visit_edge[j] = 3 ^ visit_edge[i];
				}
			} 
		}
	}
	vector<int> vres;
	for (int i = 0; i < m; ++i) {
		if (visit_edge[i] % 2 == 0) vres.push_back(i);
	}
	return vres;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 464 KB correct
4 Correct 2 ms 488 KB correct
5 Correct 4 ms 536 KB correct
6 Correct 3 ms 540 KB correct
7 Correct 3 ms 640 KB correct
8 Correct 2 ms 640 KB correct
9 Correct 2 ms 640 KB correct
10 Correct 3 ms 644 KB correct
11 Correct 3 ms 648 KB correct
12 Correct 3 ms 652 KB correct
13 Correct 2 ms 656 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 464 KB correct
4 Correct 2 ms 488 KB correct
5 Correct 4 ms 536 KB correct
6 Correct 3 ms 540 KB correct
7 Correct 3 ms 640 KB correct
8 Correct 2 ms 640 KB correct
9 Correct 2 ms 640 KB correct
10 Correct 3 ms 644 KB correct
11 Correct 3 ms 648 KB correct
12 Correct 3 ms 652 KB correct
13 Correct 2 ms 656 KB correct
14 Correct 6 ms 656 KB correct
15 Correct 5 ms 788 KB correct
16 Correct 6 ms 788 KB correct
17 Correct 4 ms 792 KB correct
18 Correct 4 ms 792 KB correct
19 Correct 4 ms 792 KB correct
20 Correct 3 ms 796 KB correct
21 Correct 4 ms 932 KB correct
22 Correct 4 ms 996 KB correct
23 Correct 4 ms 996 KB correct
24 Correct 3 ms 996 KB correct
25 Correct 3 ms 996 KB correct
26 Correct 4 ms 996 KB correct
27 Correct 3 ms 996 KB correct
28 Correct 3 ms 996 KB correct
29 Correct 3 ms 996 KB correct
30 Correct 3 ms 996 KB correct
31 Correct 3 ms 996 KB correct
32 Correct 3 ms 996 KB correct
33 Correct 4 ms 1060 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 464 KB correct
4 Correct 2 ms 488 KB correct
5 Correct 4 ms 536 KB correct
6 Correct 3 ms 540 KB correct
7 Correct 3 ms 640 KB correct
8 Correct 2 ms 640 KB correct
9 Correct 2 ms 640 KB correct
10 Correct 3 ms 644 KB correct
11 Correct 3 ms 648 KB correct
12 Correct 3 ms 652 KB correct
13 Correct 2 ms 656 KB correct
14 Correct 6 ms 656 KB correct
15 Correct 5 ms 788 KB correct
16 Correct 6 ms 788 KB correct
17 Correct 4 ms 792 KB correct
18 Correct 4 ms 792 KB correct
19 Correct 4 ms 792 KB correct
20 Correct 3 ms 796 KB correct
21 Correct 4 ms 932 KB correct
22 Correct 4 ms 996 KB correct
23 Correct 4 ms 996 KB correct
24 Correct 3 ms 996 KB correct
25 Correct 3 ms 996 KB correct
26 Correct 4 ms 996 KB correct
27 Correct 3 ms 996 KB correct
28 Correct 3 ms 996 KB correct
29 Correct 3 ms 996 KB correct
30 Correct 3 ms 996 KB correct
31 Correct 3 ms 996 KB correct
32 Correct 3 ms 996 KB correct
33 Correct 4 ms 1060 KB correct
34 Correct 155 ms 2424 KB correct
35 Correct 154 ms 2548 KB correct
36 Correct 116 ms 2636 KB correct
37 Correct 9 ms 2636 KB correct
38 Correct 173 ms 3148 KB correct
39 Correct 128 ms 3148 KB correct
40 Correct 103 ms 3148 KB correct
41 Correct 182 ms 3604 KB correct
42 Correct 160 ms 3728 KB correct
43 Correct 72 ms 3728 KB correct
44 Correct 58 ms 3728 KB correct
45 Correct 78 ms 3728 KB correct
46 Correct 51 ms 3728 KB correct
47 Correct 26 ms 3728 KB correct
48 Correct 4 ms 3728 KB correct
49 Correct 9 ms 3728 KB correct
50 Correct 25 ms 3728 KB correct
51 Correct 70 ms 3728 KB correct
52 Correct 65 ms 3728 KB correct
53 Correct 51 ms 3804 KB correct
54 Correct 77 ms 4156 KB correct
55 Correct 73 ms 4156 KB correct
56 Correct 74 ms 4156 KB correct
57 Correct 77 ms 4216 KB correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 464 KB correct
4 Correct 2 ms 488 KB correct
5 Correct 4 ms 536 KB correct
6 Correct 3 ms 540 KB correct
7 Correct 3 ms 640 KB correct
8 Correct 2 ms 640 KB correct
9 Correct 2 ms 640 KB correct
10 Correct 3 ms 644 KB correct
11 Correct 3 ms 648 KB correct
12 Correct 3 ms 652 KB correct
13 Correct 2 ms 656 KB correct
14 Correct 6 ms 656 KB correct
15 Correct 5 ms 788 KB correct
16 Correct 6 ms 788 KB correct
17 Correct 4 ms 792 KB correct
18 Correct 4 ms 792 KB correct
19 Correct 4 ms 792 KB correct
20 Correct 3 ms 796 KB correct
21 Correct 4 ms 932 KB correct
22 Correct 4 ms 996 KB correct
23 Correct 4 ms 996 KB correct
24 Correct 3 ms 996 KB correct
25 Correct 3 ms 996 KB correct
26 Correct 4 ms 996 KB correct
27 Correct 3 ms 996 KB correct
28 Correct 3 ms 996 KB correct
29 Correct 3 ms 996 KB correct
30 Correct 3 ms 996 KB correct
31 Correct 3 ms 996 KB correct
32 Correct 3 ms 996 KB correct
33 Correct 4 ms 1060 KB correct
34 Correct 155 ms 2424 KB correct
35 Correct 154 ms 2548 KB correct
36 Correct 116 ms 2636 KB correct
37 Correct 9 ms 2636 KB correct
38 Correct 173 ms 3148 KB correct
39 Correct 128 ms 3148 KB correct
40 Correct 103 ms 3148 KB correct
41 Correct 182 ms 3604 KB correct
42 Correct 160 ms 3728 KB correct
43 Correct 72 ms 3728 KB correct
44 Correct 58 ms 3728 KB correct
45 Correct 78 ms 3728 KB correct
46 Correct 51 ms 3728 KB correct
47 Correct 26 ms 3728 KB correct
48 Correct 4 ms 3728 KB correct
49 Correct 9 ms 3728 KB correct
50 Correct 25 ms 3728 KB correct
51 Correct 70 ms 3728 KB correct
52 Correct 65 ms 3728 KB correct
53 Correct 51 ms 3804 KB correct
54 Correct 77 ms 4156 KB correct
55 Correct 73 ms 4156 KB correct
56 Correct 74 ms 4156 KB correct
57 Correct 77 ms 4216 KB correct
58 Correct 2 ms 4216 KB correct
59 Correct 2 ms 4216 KB correct
60 Incorrect 119 ms 7912 KB WA in grader: NO
61 Halted 0 ms 0 KB -