oj.uz

Submission #81989

# Submission time Handle Problem Language Result Execution time Memory
81989 2018-10-28T10:32:48 Z Saboon Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 1748 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 756 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 756 KB Output is correct
2 Correct 3 ms 772 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 820 KB Expected integer, but "no" found

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 820 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 840 KB Output is correct
2 Incorrect 5 ms 840 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 840 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1352 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1352 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 1748 KB Time limit exceeded
2 Halted 0 ms 0 KB -