Submission #33904

#	Time	Username	Problem	Language	Result	Execution time	Memory
33904		imeimi2000	Simurgh (IOI17_simurgh)	C++14	100 / 100	166 ms	7864 KiB

simurgh

#include "simurgh.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pi;

struct road {
	int i, x;
};

int n, m;
const int MAXM = 500 * 499 / 2;
vector<road> edge[500];
pi es[MAXM];

bool dfsTree[MAXM];
bool backGraph[MAXM];
vector<int> dfsQ;
int par[500];
int parEdge[500];
int dep[500];
int back[500];
int backEdge[500];
int ord = 0, base;

int royal[MAXM];
int sub[500];
int uf[500];

void dfs(int x, int p) {
	dep[x] = ++ord;
	back[x] = dep[x];
	backEdge[x] = -1;
	for (road i : edge[x]) {
		if (dep[i.x] != 0) {
			if (i.x != p && dep[i.x] < back[x]) {
				back[x] = dep[i.x];
				backEdge[x] = i.i;
			}
			continue;
		}
		dfsTree[i.i] = true;
		dfsQ.push_back(i.i);
		par[i.x] = x;
		parEdge[i.x] = i.i;
		dfs(i.x, x);
		if (back[i.x] == dep[i.x]) royal[i.i] = 1;
		else if (back[i.x] < back[x]) {
			back[x] = back[i.x];
			backEdge[x] = backEdge[i.x];
		}
	}
	if (back[x] < dep[x]) backGraph[backEdge[x]] = true;
}

int find(int x) {
	if (uf[x] != x) return uf[x] = find(uf[x]);
	return x;
}

bool merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;
	uf[x] = y;
	return true;
}

int question(const vector<int> &vt) {
	vector<int> qs;
	int other = 0;
	for (int i = 0; i < n; ++i) uf[i] = i;
	for (int i : vt) {
		qs.push_back(i);
		merge(es[i].first, es[i].second);
	}
	for (int i : dfsQ) {
		if (merge(es[i].first, es[i].second)) {
			qs.push_back(i);
			if (royal[i] == 1) ++other;
		}
	}
	return count_common_roads(qs) - other;
}

void bsearch(const vector<int> &vt, int s, int e, int c) {
	if (c == 0) {
		for (int i = s; i <= e; ++i) royal[vt[i]] = -1;
		return;
	}
	if (c == e - s + 1) {
		for (int i = s; i <= e; ++i) royal[vt[i]] = 1;
		return;
	}
	vector<int> qs;
	int m = (s + e) / 2;
	for (int i = s; i <= m; ++i) qs.push_back(vt[i]);
	int d = question(qs);
	bsearch(vt, s, m, d);
	bsearch(vt, m + 1, e, c - d);
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	n = N;
	m = u.size();
	for (int i = 0; i < m; ++i) {
		es[i] = pi(u[i], v[i]);
		edge[u[i]].push_back({ i, v[i] });
		edge[v[i]].push_back({ i, u[i] });
	}
	dfs(0, -1);
	base = count_common_roads(dfsQ);
	vector<pi> es;
	for (int i = 0; i < m; ++i) {
		if (backGraph[i]) es.push_back(pi(min(dep[u[i]], dep[v[i]]), i));
	}
	sort(es.begin(), es.end());
	for (pi i : es) {
		int s = u[i.second], e = v[i.second];
		if (dep[s] < dep[e]) swap(s, e);
		int j = s;
		bool allZero = true;
		while (par[j] != e) {
			if (royal[parEdge[j]] == 0) {
				vector<int> qs;
				for (int k : dfsQ) {
					if (k != parEdge[j]) qs.push_back(k);
				}
				qs.push_back(i.second);
				sub[j] = count_common_roads(qs) - base;
				if (sub[j] != 0) {
					allZero = false;
					royal[parEdge[j]] = -sub[j];
					royal[i.second] = sub[j];
				}
			}
			else allZero = false;
			j = par[j];
		}

		vector<int> qs;
		for (int k : dfsQ) {
			if (k != parEdge[j]) qs.push_back(k);
		}
		qs.push_back(i.second);
		sub[j] = count_common_roads(qs) - base;
		if (royal[parEdge[j]] != 0) {
			allZero = false;
			royal[i.second] = royal[parEdge[j]] + 2 * sub[j];
		}
		else if (sub[j] != 0) {
			allZero = false;
			royal[parEdge[j]] = -sub[j];
			royal[i.second] = sub[j];
		}
		if (allZero) {
			j = s;
			while (j != e) {
				royal[parEdge[j]] = -1;
				j = par[j];
			}
			royal[i.second] = -1;
			continue;
		}
		j = s;
		while (j != e) {
			if (royal[parEdge[j]] == 0) royal[parEdge[j]] = royal[i.second] - 2 * sub[j];
			j = par[j];
		}
	}

	for (int i = 0; i < n; ++i) {
		vector<int> es;
		for (road j : edge[i]) {
			if (royal[j.i] == 0) es.push_back(j.i);
		}
		bsearch(es, 0, es.size() - 1, question(es));
	}
	vector<int> ret;
	for (int i = 0; i < m; ++i) {
		if (royal[i] == 1) ret.push_back(i);
	}
	return ret;
}

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