Submission #81989

#	Time	Username	Problem	Language	Result	Execution time	Memory
81989		Saboon	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	1055 ms	1748 KiB

indcyc

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e4 + 10;
const int mod = 1e6 + 7;

vector <int> g[maxn];

int n;

bool visited[maxn];
void dfs (int v, int mask, bool print = 0) {
	visited[v] = 1;
	for (auto u : g[v])
		if (mask & (1 << u) and !visited[u])
			dfs (u, mask, print);
	if (print)
		cout << v + 1 << " ";
	
}

bool check (int mask) {
	memset (visited, 0, sizeof visited);
	for (int v = 0; v < n; v++) {
		if ((mask & (1 << v)) == 0)
			continue;
		int cnt = 0;
		for (auto u : g[v]) {
			if (mask & (1 << u))
				cnt ++;
		}
		if (cnt != 2)
			return 0;
	}
	int cnt = 0;
	for (int v = 0; v < n; v++) {
		if (!visited[v] and mask & (1 << v)) {
			dfs (v, mask);
			cnt ++;
		}
	}
	return cnt == 1;
}

int bitmask (int mask) {
	int ret = 0;
	while (mask) {
		ret ++;
		mask -= mask & -mask;
	}
	return ret;
}

int main() {
	int m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int v, u;
		cin >> v >> u;
		v --, u --;
		g[v].PB (u);
		g[u].PB (v);
	}
	for (int mask = 0; mask < (1 << n); mask++) {
		if (bitmask (mask) > 3 and check (mask)) {
			memset (visited, 0, sizeof visited);
			for (int v = 0; v < n; v++)
				if (!visited[v] and mask & (1 << v))
					dfs (v, mask, 1);
			return 0;
		}
	}
	cout << "no" << endl;
}

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