Submission #1268091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268091		LaMatematica14	Simurgh (IOI17_simurgh)	C++20	0 / 100	62 ms	3396 KiB

simurgh

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

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

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

	vector<int> golden;

	vector<vector<int>> connected(n);
	for (int i = 0; i < n; i++) {
		//cout << "Node " << i << endl;
		vector<int> sp = find_without_node(i);
		int mean_quan = -1;
		vector<int> und, mean, over;
		if (!connected[i].empty()) {
			sp.push_back(connected[i][0]);
			mean_quan = count_common_roads(sp)-1;
			sp.pop_back();
			over.push_back(-1);
		}
		for (auto x : adj[i]) {
			if (x.first < i) continue;
			sp.push_back(x.second);
			int ans = count_common_roads(sp);
			sp.pop_back();
			if (mean_quan == -1) {
				mean_quan = ans;
				mean.push_back(x.second);
			} 
			else if (ans > mean_quan) over.push_back(x.second);
			else if (ans == mean_quan) mean.push_back(x.second);
			else  und.push_back(x.second);
		}

		if (over.empty()) {
			while (mean.size() >= 1) {
				//cout << "Into golden from mean: " << mean.back() << endl;
				golden.push_back(mean.back());
				connected[max(u[mean.back()], v[mean.back()])].push_back(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()])].push_back(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