Submission #559688

#	Time	Username	Problem	Language	Result	Execution time	Memory
559688		nonsensenonsense1	Simurgh (IOI17_simurgh)	C++17	51 / 100	141 ms	4084 KiB

simurgh

#include "simurgh.h"
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 500;
const int E = N * N;
std::vector<std::pair<int, int> > g[N];
int u[N], val[N];
bool know[E], ans[E];

std::vector<int> edg;
int it;
void dfs(int v) {
	u[v] = it;
	for (int i = 0; i < (int)g[v].size(); ++i) if (!u[g[v][i].first]) {
		edg.push_back(g[v][i].second);
		dfs(g[v][i].first);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u_, std::vector<int> v_) {
	for (int i = 0; i < (int)u_.size(); ++i) {
		g[u_[i]].push_back(std::make_pair(v_[i], i));
		g[v_[i]].push_back(std::make_pair(u_[i], i));
	}
	for (int i = 0; i < n; ++i) {
		memset(u, 0, n << 2);
		u[i] = 1;
		it = 0;
		for (int j = 0; j < n; ++j) if (!u[j]) {
			++it;
			dfs(j);
		}
		for (int iit = 1; iit <= it; ++iit) {
			for (int j = 0;; ++j) if (u[g[i][j].first] == iit) {
				edg.push_back(g[i][j].second);
				break;
			}
		}
		for (int iit = 1; iit <= it; ++iit) {
			int fi = edg[n - 2 - it + iit];
			edg.erase(edg.begin() + n - 2 - it + iit);
			int mn = ~(1 << 31), mx = 0, real = -1;
			bool askonce = 0;
			for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit) {
				if (!know[g[i][j].second] || !askonce) {
					edg.push_back(g[i][j].second);
					val[j] = count_common_roads(edg);
					if (know[g[i][j].second]) {
						real = val[j] - ans[g[i][j].second];
						askonce = 1;
					}
					mn = std::min(mn, val[j]);
					mx = std::max(mx, val[j]);
					edg.pop_back();
				}
			}
			if (real == -1) real = mn - (mn == mx);
			for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit && !know[g[i][j].second]) {
				know[g[i][j].second] = 1;
				ans[g[i][j].second] = val[j] != real;
			}
			edg.insert(edg.begin() + n - 2 - it + iit, fi);
		}
		edg.clear();
	}
	std::vector<int> ret;
	for (int i = 0; i < (int)u_.size(); ++i) if (ans[i]) ret.push_back(i);
	return ret;
}

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