제출 #559680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559680		nonsensenonsense1	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	212 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[edg.size() - g[i].size() + iit - 1];
			edg.erase(edg.end() - g[i].size() + iit - 1);
			int mn = ~(1 << 31);
			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]) {
						mn = val[j] - ans[g[i][j].second];
						askonce = 1;
					}
					mn = std::min(mn, val[j]);
					edg.pop_back();
				}
			}
			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] != mn;
			}
			edg.insert(edg.end() - g[i].size() + 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: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30