Submission #767693

#	Time	Username	Problem	Language	Result	Execution time	Memory
767693		SanguineChameleon	Simurgh (IOI17_simurgh)	C++17	51 / 100	108 ms	4028 KiB

simurgh

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

const int maxn = 5e2 + 20;
const int maxm = maxn * maxn / 2;
vector<pair<int, int>> adj[maxn];
bool tree[maxm];
int flag[maxm];
int comp[maxn];

void dfs1(int u) {
	flag[u] = true;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (!flag[v]) {
			tree[id] = true;
			dfs1(v);
		}
	}
}

void dfs2(int u, int p) {
	comp[u] = 1;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (tree[id] && v != p) {
			dfs2(v, u);
		}
	}
}

mt19937 gen(69420);

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	for (int i = 0; i < m; i++) {
		adj[u[i]].emplace_back(v[i], i);
		adj[v[i]].emplace_back(u[i], i);
	}
	vector<int> order(m);
	for (int i = 0; i < m; i++) {
		order[i] = i;
	}
	shuffle(order.begin(), order.end(), gen);
	dfs1(0);
	for (int i = 0; i < m; i++) {
		flag[i] = -1;
	}
	vector<int> res;
	for (int i = 0; i < m; i++) {
		if (tree[i]) {
			res.push_back(i);
		}
	}
	while (true) {
		for (int i = 0; i < n - 1; i++) {
			if (flag[res[i]] == -1) {
				tree[res[i]] = false;
				res.erase(res.begin() + i);
				break;
			}
		}
		if ((int)res.size() == n - 1) {
			break;
		}
		for (int i = 0; i < n; i++) {
			comp[i] = 0;
		}
		dfs2(0, -1);
		vector<pair<int, int>> cnt;
		int good = -1;
		for (int i = 0; i < m; i++) {
			if (comp[u[i]] != comp[v[i]] && flag[i] == 1) {
				good = i;
				break;
			}
		}
		if (good == -1) {
			int mx = -1;
			for (int k = 0; k < m; k++) {
				int i = order[k];
				if (comp[u[i]] != comp[v[i]] && flag[i] == -1) {
					res.push_back(i);
					cnt.emplace_back(count_common_roads(res), i);
					res.pop_back();
					mx = max(mx, cnt.back().first);
					if ((int)cnt.size() >= 2 && cnt.back().first != cnt.end()[-2].first) {
						break;
					}
				}
			}
			for (auto p: cnt) {
				if (p.first == mx) {
					good = p.second;
					flag[p.second] = 1;
				}
				else {
					flag[p.second] = 0;
				}
			}
		}
		tree[good] = true;
		res.push_back(good);
	}
	return res;
}

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