oj.uz

Submission #566294

# Submission time Handle Problem Language Result Execution time Memory
566294 2022-05-22T08:17:57 Z Temmie Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 212 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[i] == use[i]) {
				vals[i] = val;
				continue;
			}
			int tmp = use[i];
			use[i] = can[j];
			vals[i] = 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -