oj.uz

Submission #566298

# Submission time Handle Problem Language Result Execution time Memory
566298 2022-05-22T08:20:38 Z Temmie Simurgh (IOI17_simurgh) C++17
30 / 100
 150 ms 2348 KB 
//#include "public/cpp/simurgh.h"
#include "simurgh.h"

#include <bits/stdc++.h>

//int count_common_roads(std::vector <int> r) { return 0; }

struct Dsu {
	std::vector <int> p;
	Dsu(int size) {
		p.resize(size);
		std::iota(p.begin(), p.end(), 0);
	}
	int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	void unite(int u, int v) {
		p[find(v)] = find(u);
	}
	void clear() {
		std::iota(p.begin(), p.end(), 0);
	}
};

std::vector <int> find_roads(int n, std::vector <int> u, std::vector <int> v) {
	int m = u.size();
	std::vector <int> use;
	Dsu dsu(n);
	for (int i = 0; i < m; i++) {
		if (dsu.find(u[i]) != dsu.find(v[i])) {
			dsu.unite(u[i], v[i]);
			use.push_back(i);
		}
	}
	assert((int) use.size() == n - 1);
	int val = count_common_roads(use);
	for (int i = 0; i < n - 1; i++) {
		dsu.clear();
		for (int j = 0; j < n - 1; j++) {
			if (i != j) {
				assert(dsu.find(u[use[j]]) != dsu.find(v[use[j]]));
				dsu.unite(u[use[j]], v[use[j]]);
			}
		}
		std::vector <int> can;
		for (int j = 0; j < m; j++) {
			if (dsu.find(u[j]) != dsu.find(v[j])) {
				can.push_back(j);
			}
		}
		assert(can.size());
		std::vector <int> vals(can.size(), -1);
		for (int j = 0; j < (int) can.size(); j++) {
			assert(dsu.find(u[can[j]]) != dsu.find(v[can[j]]));
			if (can[j] == use[i]) {
				vals[j] = val;
				continue;
			}
			int tmp = use[i];
			use[i] = can[j];
			vals[j] = count_common_roads(use);
			use[i] = tmp;
		}
		for (int j = 0; j < (int) can.size(); j++) {
			if (vals[j] > val) {
				use[i] = can[j];
				val = vals[j];
			}
		}
	}
	return use;
}

//int main() {
	
//}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 300 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 296 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 9 ms 340 KB correct
15 Correct 7 ms 332 KB correct
16 Correct 7 ms 304 KB correct
17 Correct 10 ms 212 KB correct
18 Correct 4 ms 212 KB correct
19 Correct 11 ms 328 KB correct
20 Correct 10 ms 304 KB correct
21 Correct 7 ms 212 KB correct
22 Correct 5 ms 212 KB correct
23 Correct 5 ms 212 KB correct
24 Correct 4 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 212 KB correct
27 Correct 5 ms 296 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 6 ms 304 KB correct
31 Correct 7 ms 212 KB correct
32 Correct 6 ms 212 KB correct
33 Correct 5 ms 212 KB correct
34 Incorrect 150 ms 1100 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 300 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 296 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 9 ms 340 KB correct
15 Correct 7 ms 332 KB correct
16 Correct 7 ms 304 KB correct
17 Correct 10 ms 212 KB correct
18 Correct 4 ms 212 KB correct
19 Correct 11 ms 328 KB correct
20 Correct 10 ms 304 KB correct
21 Correct 7 ms 212 KB correct
22 Correct 5 ms 212 KB correct
23 Correct 5 ms 212 KB correct
24 Correct 4 ms 212 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 212 KB correct
27 Correct 5 ms 296 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 6 ms 304 KB correct
31 Correct 7 ms 212 KB correct
32 Correct 6 ms 212 KB correct
33 Correct 5 ms 212 KB correct
34 Incorrect 150 ms 1100 KB WA in grader: NO
35 Halted 0 ms 0 KB -