Submission #566298

#	Time	Username	Problem	Language	Result	Execution time	Memory
566298		Temmie	Simurgh (IOI17_simurgh)	C++17	30 / 100	150 ms	2348 KiB

simurgh

//#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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30