Submission #51898

#	Time	Username	Problem	Language	Result	Execution time	Memory
51898		aome	Simurgh (IOI17_simurgh)	C++17	51 / 100	182 ms	7912 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

const int N = 510;
const int M = 510 * 510 / 2;

int n, m;
int h[N];
pair<int, int> par[N];
bool visit[N];
bool tree_edge[M];
int visit_edge[M];
pair<int, int> e[M];
vector< pair<int, int> > G[N];

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (visit[v.first]) continue;
		tree_edge[v.second] = 1, h[v.first] = h[u] + 1;
		par[v.first] = {u, v.second}, dfs(v.first);  
	}
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
	n = _n, m = _u.size();
	for (int i = 0; i < m; ++i) {
		e[i] = {_u[i], _v[i]};
		G[_u[i]].push_back({_v[i], i});
		G[_v[i]].push_back({_u[i], i});
	}
	dfs(0);
	vector<int> vec;
	for (int i = 0; i < m; ++i) {
		if (tree_edge[i]) vec.push_back(i);
	}
	int val = count_common_roads(vec);
	for (int i = 0; i < m; ++i) {
		if (h[e[i].first] > h[e[i].second]) swap(e[i].first, e[i].second);
		if (tree_edge[i]) continue;
		int cur = e[i].second;
		vector<int> buf;
		while (cur != e[i].first) {
			buf.push_back(par[cur].second), cur = par[cur].first;
		}
		int id = -1;
		for (auto j : buf) {
			if (visit_edge[j]) id = j;
		}
		if (id == -1) {
			for (auto j : buf) {
				vector<int> ask = vec;
				for (auto &k : ask) if (k == j) k = i;
				int tmp = count_common_roads(ask);
				if (tmp != val) {
					visit_edge[i] = (tmp > val) + 1;
					visit_edge[j] = 3 ^ visit_edge[i];
					// 1 : not loyal, 2 : loyal
				}
			}
			if (!visit_edge[i]) visit_edge[i] = 1;
			for (auto j : buf) {
				if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
			}
		}
		else {
			vector<int> ask = vec;
			for (auto &j : ask) if (j == id) j = i;
			int tmp = count_common_roads(ask);
			if (tmp == val) visit_edge[i] = visit_edge[id];
			else visit_edge[i] = 3 ^ visit_edge[id];
			for (auto j : buf) {
				if (!visit_edge[j]) {
					vector<int> ask = vec;
					for (auto &k : ask) if (k == j) k = i;
					int tmp = count_common_roads(ask);
					if (tmp == val) visit_edge[j] = visit_edge[i];
					else visit_edge[j] = 3 ^ visit_edge[i];
				}
			} 
		}
	}
	vector<int> vres;
	for (int i = 0; i < m; ++i) {
		if (visit_edge[i] % 2 == 0) vres.push_back(i);
	}
	return vres;
}

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