oj.uz

Submission #74746

# Submission time Handle Problem Language Result Execution time Memory
74746 2018-09-07T05:00:41 Z shoemakerjo Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 22 ms 5796 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>

const int maxn = 100010;
int N, M;
const int mod = 1000000007;
int nums[maxn];
vector<int> adj[maxn];
int par[maxn];

int findset(int a) {
	if (par[a] == a) return a;
	return par[a] = findset(par[a]);
}

void unionset(int a, int b) {
	a = findset(a);
	b = findset(b);
	if (a == b) return;
	if (rand() % 2) {
		par[a] = b;
	}
	else par[b] = a;
}

bool vis[maxn];
// int val;

void dfs(int u, int p) {
	vis[u] = true;
	for (int val : adj[u]) {
		if (val != p) {
			dfs(val, u);
			nums[u] = (nums[val]+nums[u])%mod;
		}

	}
	if (nums[u] == 0 && p != -1) {
		cout << u << " " << p << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) par[i] = i;
	srand(23); //want deterministic for now

	int x, y;
	int cur;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		if (findset(x) != findset(y)) {
			adj[x].push_back(y);
			adj[y].push_back(x);
			unionset(x, y);
		}
		else {
			cur = rand()%mod;
			nums[x] += cur + 0LL;
			nums[y] += mod-cur + 0LL;
			nums[x]%=mod;
			nums[y]%=mod;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!vis[i]) dfs(i, -1);
	}
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Too short sequence
2 Incorrect 4 ms 2848 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2848 KB Too short sequence

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2848 KB Too short sequence
2 Incorrect 4 ms 2848 KB Unexpected end of file - token expected

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3000 KB Too short sequence

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3000 KB Too short sequence
2 Incorrect 4 ms 3120 KB Unexpected end of file - token expected

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3120 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3120 KB Too short sequence
2 Incorrect 4 ms 3240 KB Unexpected end of file - token expected

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3580 KB Too short sequence
2 Correct 7 ms 3820 KB Too short sequence
3 Incorrect 13 ms 4096 KB Wrong answer on graph without induced cycle
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4332 KB Too short sequence
2 Incorrect 9 ms 4484 KB Unexpected end of file - token expected

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5152 KB Too short sequence
2 Incorrect 22 ms 5796 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -