oj.uz

Submission #74737

# Submission time Handle Problem Language Result Execution time Memory
74737 2018-09-07T04:44:16 Z shoemakerjo Pipes (CEOI15_pipes) C++14
100 / 100
 1296 ms 7920 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define maxn 100010
int N, M;
const int mod = 1000000007;
ll nums[maxn];
vector<vector<int>> adj(maxn);
vector<pii> ans;
int par[maxn];
ll csum[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];

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

	}
	if (csum[u] == 0 && p != -1) {
		ans.push_back(pii(u, p));
	}
}

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

	for (int i = 1; i <= N; i++) {
		if (!vis[i]) dfs(i, -1);
	}
	for (pii pa : ans) {
		cout << pa.first << " " << pa.second << endl;
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3056 KB Output is correct
2 Correct 7 ms 2944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 2904 KB Output is correct
2 Correct 105 ms 2900 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3164 KB Output is correct
2 Correct 212 ms 3152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 3912 KB Output is correct
2 Correct 261 ms 4216 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6292 KB Output is correct
2 Correct 349 ms 6268 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 6872 KB Output is correct
2 Correct 642 ms 6916 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 7804 KB Output is correct
2 Correct 873 ms 7920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 7804 KB Output is correct
2 Correct 1062 ms 7832 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 7592 KB Output is correct
2 Correct 1244 ms 7876 KB Output is correct