Submission #1268439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268439		LaMatematica14	Simurgh (IOI17_simurgh)	C++20	0 / 100	1 ms	324 KiB

simurgh

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

vector<int> find_roads(int n, vector<int> u, vector<int> v) {\
	int m = u.size();
	vector<vector<pair<int, int>>> adj(n);
	vector<vector<int>> mat(n, vector<int> (n, -1));
	for (int i = 0; i < u.size(); i++) {
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
		mat[u[i]][v[i]] = i;
		mat[v[i]][u[i]] = i;
	}

	auto find_without_node = [&](int w) -> pair<vector<vector<int>>, vector<vector<int>>> {
		int r = 0;
		if (r == w) r = 1;
		vector<vector<int>> spanning;
		vector<vector<int>> cc;
		stack<int> st; st.push(r);
		vector<bool> visited(n, 0); visited[r] = 1;
		do {
			spanning.push_back({});
			cc.push_back({});
			visited[w] = 0; 
			while (!st.empty()) {
				int a = st.top();
				st.pop(); cc.back().push_back(a);
				for (auto x : adj[a]) {
					if (visited[x.first]) continue;
					visited[x.first] = 1;
					if (x.first == w) {
						spanning.back().push_back(x.second+m);
						continue;
					}
					st.push(x.first);
					spanning.back().push_back(x.second);
				}
			}
			for (int i = 0; i < n; i++) {
				if (visited[i] == 0) {
					visited[i] = 1;
					st.push(i); break;
				}
			}
		} while (!st.empty());
		return {spanning, cc};
	};

	vector<int> golden;

	vector<set<int>> connected(n);
	for (int i = 0; i < n; i++) {
		//cout << "Node " << i << endl;
		auto [span, cc_nodes] = find_without_node(i);
		vector<int> together;
		vector<int> tocc;
		for (auto y : span) {
			for (auto z : y) {
				if (z < m) together.push_back(z);
				else tocc.push_back(z-m);
			}
		}
		assert(tocc.size() == span.size());

		for (int k = 0; k < span.size(); k++) {
			vector<int> sp = together;
			for (int p = 0; p < span.size(); p++) {
				if (p == k) continue;
				sp.push_back(tocc[p]);
			}
			int mean_quan = -1;
			vector<int> und, mean, over;
			for (auto x : cc_nodes[k]) {
				if (mat[i][x] == -1) continue;
				int edge = mat[i][x];
				if (!connected[i].count(edge) && x < i) continue;
				int to_add = edge;
				if (connected[i].count(edge)) to_add = -1;
				sp.push_back(edge);
				int ans = count_common_roads(sp);
				sp.pop_back();
				if (mean_quan == -1) {
					mean_quan = ans;
					mean.push_back(to_add);
				} 
				else if (ans > mean_quan) over.push_back(to_add);
				else if (ans == mean_quan) mean.push_back(to_add);
				else  und.push_back(to_add);
			}

			if (over.empty()) {
				while (mean.size() >= 1) {
					if (mean.back() == -1) break;
					//cout << "Into golden from mean: " << mean.back() << endl;
					golden.push_back(mean.back());
					connected[max(u[mean.back()], v[mean.back()])].insert(mean.back());
					mean.pop_back();
				}
			} else {
				while (over.size() >= 1) {
					if (over.back() == -1) break;
					//cout << "Into golden from over: " << over.back() << endl;
					golden.push_back(over.back());
					connected[max(u[over.back()], v[over.back()])].insert(over.back());
					over.pop_back();
				}
			}
		}

	}
	//cout << "Golden set size: " << golden.size() << endl;
	assert(golden.size() == n-1);
	return golden;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30