Submission #768611

#	Time	Username	Problem	Language	Result	Execution time	Memory
768611		SanguineChameleon	Simurgh (IOI17_simurgh)	C++17	0 / 100	19 ms	16480 KiB

simurgh

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

const int maxN = 5e2 + 20;
const int maxM = maxN * maxN / 2;
pair<int, int> edges[maxN];
vector<pair<int, int>> adj[maxM];
pair<int, int> high[maxN];
int par[maxN];
int par_id[maxN];
int depth[maxN];
int flag[maxM];
vector<int> cycle[maxM];
vector<int> tree;
int N, M;

void dfs(int u, int p) {
	flag[u] = true;
	high[u] = make_pair(depth[u], -1);
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (v == p) {
			continue;
		}
		if (!flag[v]) {
			depth[v] = depth[u] + 1;
			par[v] = u;
			par_id[v] = id;
			dfs(v, u);
			high[u] = min(high[u], high[v]);
		}
		else {
			high[u] = min(high[u], make_pair(depth[v], id));
		}
	}
}

int query_cycle(int i, int j) {
	tree.erase(find(tree.begin(), tree.end(), j));
	tree.push_back(i);
	int res = count_common_roads(tree);
	tree.pop_back();
	tree.push_back(j);
	return res;
}

int root(int u) {
	if (par[u] == -1) {
		return u;
	}
	else {
		return par[u] = root(par[u]);
	}
}

bool join(int u, int v) {
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		return false;
	}
	if (depth[ru] > depth[rv]) {
		swap(ru, rv);
	}
	par[ru] = rv;
	if (depth[ru] == depth[rv]) {
		depth[rv]++;
	}
	return true;
}

int query_tree(vector<int> query) {
	for (int i = 0; i < N; i++) {
		depth[i] = 0;
		par[i] = -1;
	}
	for (auto id: query) {
		join(edges[id].first, edges[id].second);
	}
	int extra = 0;
	for (auto id: tree) {
		if (join(edges[id].first, edges[id].second)) {
			extra += flag[id];
			query.push_back(id);
		}
	}
	return count_common_roads(query) - extra;
}

vector<int> find_roads(int _N, vector<int> U, vector<int> V) {
	N = _N;
	M = U.size();
	for (int i = 0; i < M; i++) {
		edges[i] = make_pair(U[i], V[i]);
		adj[U[i]].emplace_back(V[i], i);
		adj[V[i]].emplace_back(U[i], i);
	}
	dfs(0, -1);
	for (int i = 0; i < N; i++) {
		adj[i].clear();
	}
	for (int i = 0; i < M; i++) {
		flag[i] = -1;
	}
	for (int i = 1; i < N; i++) {
		tree.push_back(par_id[i]);
		if (high[i].second == -1) {
			flag[par_id[i]] = 1;
		}
		else {
			cycle[high[i].second].push_back(par_id[i]);
		}
	}
	for (int i = 0; i < M; i++) {
		if (cycle[i].empty()) {
			continue;
		}
		int u = U[i];
		int v = V[i];
		if (depth[u] < depth[v]) {
			swap(u, v);
		}
		while (par[u] != v) {
			u = par[u];
		}
		vector<pair<int, int>> cnt;
		cnt.emplace_back(par_id[u], query_cycle(i, par_id[u]));
		for (auto j: cycle[i]) {
			cnt.emplace_back(j, query_cycle(i, j));
		}
		for (auto p1: cnt) {
			for (auto p2: cnt) {
				adj[p1.first].emplace_back(p2.first, p1.second - p2.second);
			}
		}
	}
	for (int i = 0; i < M; i++) {
		if (flag[i] != -1) {
			continue;
		}
		for (auto e: adj[i]) {
			if (e.second == -1) {
				flag[i] = 1;
			}
			if (e.second == 1) {
				flag[i] = 0;
			}
		}
		if (flag[i] != -1) {
			deque<int> q;
			q.push_back(i);
			while (!q.empty()) {
				int u = q.front();
				q.pop_front();
				for (auto e: adj[u]) {
					int v = e.first;
					if (flag[v] == -1) {
						flag[v] = flag[u] + e.second;
						q.push_back(v);
					}
				}
			}
		}
	}
	for (auto id: tree) {
		if (flag[id] == -1) {
			flag[id] = 0;
		}
	}
	vector<int> res;
	for (int i = 0; i < M; i++) {
		if (query_tree(vector<int>(1, i))) {
			res.push_back(i);
		}
	}
	return res;
}

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