Submission #1076043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076043		NeroZein	Simurgh (IOI17_simurgh)	C++17	30 / 100	216 ms	3028 KiB

simurgh

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

vector<int> find_roads(int n, vector<int> eu, vector<int> ev) {
	
	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);
		}
		p[u] = v;
		sz[v] += sz[u];
		return true;
	};
	
	auto init_dsu = [&]() {
		iota(p.begin(), p.end(), 0);
		fill(sz.begin(), sz.end(), 1);
	};
	
	int idd;
	vector<vector<int>> g(n); 
	vector<int> in(n), out(n);
	function<void(int, int)> dfs = [&](int v, int prnt) {
		in[v] = idd++;
		for (int u : g[v]) {
			if (u == prnt) {
				continue;
			}
			dfs(u, v); 
		}
		out[v] = idd - 1;
	};
	auto in_subtree = [&](int prnt, int v) {
		return in[prnt] <= in[v] && out[prnt] >= out[v];
	};
	
	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);
		}
	}
	
	auto traverse = [&]() {
		for (int i = 0; i < n; ++i) {
			g[i].clear();
		}
		for (int i = 0; i < n - 1; ++i) {
			int label = in_tree[i];
			g[eu[label]].push_back(ev[label]);
			g[ev[label]].push_back(eu[label]);
		}
		idd = 0;
		dfs(0, 0); 
	};
	
	int x = count_common_roads(in_tree);
	vector<int> state(m, -1);
	for (int i : out_tree) {
		vector<int> unknown;
		state[i] = 0;
		traverse();
		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);
			int ru = eu[label], rv = ev[label];
			if (in[ru] < in[rv]) {//u is a parent for v
				swap(ru, rv); 
			}
			int cnt = 0; 
			for (int k : {eu[i], ev[i]}) {
				cnt += in_subtree(ru, k);
			}
			
			//~ simulate(tmp); 
			if (cnt != 1) {
				continue; 
			}
			int y = count_common_roads(tmp);
			if (state[label] == -1) {
				if (y > x) {
					state[label] = 0;
					state[i] = 1;
					in_tree = tmp;
					x = y;
					break;
				} 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;
				}
				assert(state[label] == 0);
				if (y > x) {
					x = y; 
					state[i] = 1;
					in_tree = tmp;
				} else {
					assert(y == x);
					state[i] = 0;//doesn't matter
				}
				break;
			}
		}
		for (int j : unknown) {
			state[j] = state[i];
		}
	}
	return in_tree;
}
//~ int common = count_common_roads(r);

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