Submission #767690

#	Time	Username	Problem	Language	Result	Execution time	Memory
767690		SanguineChameleon	Simurgh (IOI17_simurgh)	C++17	30 / 100	63 ms	4340 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);
		}
	}
}

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);
	}
	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);
		pair<int, int> mx = make_pair(-1, -1);
		for (int i = 0; i < m; i++) {
			if (comp[u[i]] != comp[v[i]]) {
				res.push_back(i);
				int cnt = count_common_roads(res);
				if (cnt > mx.first) {
					if (mx.second != -1) {
						flag[mx.second] = 0;
					}
					flag[i] = 1;
					mx = make_pair(cnt, i);
				}
				res.pop_back();
			}
		}
		tree[mx.second] = true;
		res.push_back(mx.second);
	}
	return res;
}

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