oj.uz

Submission #67823

# Submission time Handle Problem Language Result Execution time Memory
67823 2018-08-15T10:34:32 Z polyfish Potemkin cycle (CEOI15_indcyc) C++14
70 / 100
 1000 ms 6252 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));
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 660 KB Output is correct
2 Correct 2 ms 660 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 672 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 676 KB Output is correct
2 Correct 28 ms 688 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 948 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 20 ms 1180 KB Output is correct
4 Correct 472 ms 1524 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1524 KB Output is correct
2 Correct 321 ms 1524 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2848 KB Output is correct
2 Correct 14 ms 2848 KB Output is correct
3 Execution timed out 1081 ms 3756 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 3756 KB Output is correct
2 Execution timed out 1081 ms 3756 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4356 KB Output is correct
2 Correct 164 ms 6176 KB Output is correct
3 Execution timed out 1072 ms 6252 KB Time limit exceeded
4 Halted 0 ms 0 KB -