Submission #67773

# Submission time Handle Problem Language Result Execution time Memory
67773 2018-08-15T09:47:12 Z polyfish Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
1000 ms 448456 KB
//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));
	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));
	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(2);
	for (int i=1; i<=n; ++i) {
		if (solve(i)) {
			ok = true;
			break;
		}
	}
	if (!ok)
		cout << "no";
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 415920 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 415920 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 415920 KB Output is correct
2 Execution timed out 1109 ms 416564 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 426052 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1107 ms 448456 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 448456 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 448456 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 51 ms 448456 KB Output is correct
2 Correct 160 ms 448456 KB Output is correct
3 Execution timed out 1110 ms 448456 KB Time limit exceeded
4 Halted 0 ms 0 KB -