Submission #1075903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075903		NeroZein	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	348 KiB

simurgh

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

vector<int> find_roads(int n, vector<int> eu, vector<int> ev) {
	
	int cc;
	vector<int> p(n), sz(n);
	
	function<int(int)> get = [&](int v) {
		return p[v] = (p[v] == v ? v : get(p[v]));
	};
	
	auto unite = [&](int u, int v) {
		u = get(u); v = get(v);
		if (u == v) {
			return false;
		}
		if (sz[u] > sz[v]) {
			swap(u, v);
		}
		--cc;
		p[u] = v;
		sz[v] += sz[u];
		return true;
	};
	
	auto init_dsu = [&]() {
		cc = n;
		iota(p.begin(), p.end(), 0);
		fill(sz.begin(), sz.end(), 1);
	};
	
	auto simulate = [&](vector<int> edges) {
		assert((int) edges.size() == n - 1); 
		init_dsu();
		for (int i = 0; i < n - 1; ++i) {
			unite(eu[i], ev[i]);
		}
	};
	
	int m = (int) eu.size();
	init_dsu();
	vector<int> in_tree, out_tree;
	for (int i = 0; i < m; ++i) {
		if (unite(eu[i], ev[i])) {
			in_tree.push_back(i);
		} else {
			out_tree.push_back(i);
		}
	}
	
	int x = count_common_roads(in_tree);
	vector<int> state(m, -1);
	for (int i : out_tree) {
		vector<int> unknown;
		state[i] = 0;
		assert((int) in_tree.size() == n - 1); 
		for (int j = 0; j < n - 1; ++j) {
			int label = in_tree[j];
			vector<int> tmp = in_tree;
			tmp.erase(tmp.begin() + j);
			tmp.push_back(i);
			simulate(tmp); 
			if (cc != 1) {
				continue; 
			}
			int y = count_common_roads(tmp);
			if (state[label] == -1) {
				if (y > x) {
					state[label] = 0;
					state[i] = 1;
					in_tree = tmp;
				} else if (y == x) {
					unknown.push_back(label);
				} else {//y < x
					state[label] = 1;
					state[i] = 0;//doesn't matter
					break; 
				}
			} else {
				if (state[label] == 1) {
					continue;
				}
				//state[label] = 0
				if (y > x) {
					state[i] = 1;
					in_tree = tmp;
				} else {
					assert(y == x);
					state[i] = 0;//doesn't matter
				}
				break;
			}
		}
		for (int label : unknown) {
			state[label] = state[i]; 
		}
	}
	return in_tree;
}
//~ int common = count_common_roads(r);

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