Submission #67823

#	Time	Username	Problem	Language	Result	Execution time	Memory
67823		polyfish	Potemkin cycle (CEOI15_indcyc)	C++14	70 / 100	1081 ms	6252 KiB

indcyc

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 1002;

int n, m, nCC, ccID[MAX_N], T[MAX_N];
bool avail[MAX_N], d[MAX_N], a[MAX_N][MAX_N];
vector<int> g[MAX_N], CC[MAX_N];

void enter() {
	cin >> n >> m;
	for (int i=1; i<=m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		a[u][v] = a[v][u] = true;
	}
}

void trace(int u, int fn) {
	if (u==fn)
		return;
	cout << u << ' ';
	trace(T[u], fn);
}

void find_result(int mid, int l, int r) {
	// cerr << l << ' ' << mid << ' ' << r << '\n';
	// return;
	memset(d, false, sizeof(d));
	memset(T, 0, sizeof(T));
	d[l] = true;
	d[mid] = true;
	for (auto v : g[mid])
		if (v!=l && v!=r)
			d[v] = true;
	queue<int> qu;
	qu.push(l);
	while (qu.size()) {
		int u = qu.front();
		qu.pop();
		for (auto v : g[u]) {
			if (!d[v]) {
				d[v] = true;
				T[v] = u;
				qu.push(v);
			}
		}
	}
	cout << l << ' ' << mid << ' ';
	trace(r, l);
}

void visit(int u) {
	avail[u] = false;
	ccID[u] = nCC;
	for (auto v : g[u])
		if (avail[v])
			visit(v);
}

bool solve(int u) {
	memset(avail, true, sizeof(avail));
	memset(ccID, 0, sizeof(ccID));
	for (int i=1; i<=nCC; ++i)
		CC[i].clear();
	nCC = 0;
	for (auto v : g[u])
		avail[v] = false;
	avail[u] = false;
	for (int i=1; i<=n; ++i) {
		if (avail[i]) {
			++nCC;
			visit(i);
		}
	}
	for (auto v : g[u]) {
		for (auto v2 : g[v])
			if (!a[v2][u])
				CC[ccID[v2]].push_back(v);
	}
	for (int i=1; i<=nCC; ++i) {
		for (auto v1 : CC[i]) {
			for (auto v2 : CC[i]) {
				if (v1!=v2 && !a[v1][v2]) {
					//cerr << i << ' ' << v1 << ' ' << v2 << '\n';
					find_result(u, v1, v2);
					return true;
				}
			}
		}
	}
	return false;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	bool ok = false;
	//solve(3);
	for (int i=1; i<=n; ++i) {
		if (solve(i)) {
			ok = true;
			break;
		}
	}
	if (!ok)
		cout << "no";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10