oj.uz

Submission #784224

# Submission time Handle Problem Language Result Execution time Memory
784224 2023-07-15T21:35:11 Z NK_ Pipes (CEOI15_pipes) C++17
100 / 100
 304 ms 13992 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;

int d[10];
int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		ch = getchar();
	}
	int v = 0;
	while ('0' <= ch && ch <= '9') {
		v = v * 10 + (int) (ch - '0');
		ch = getchar();
	}
	return v;
}
 
void write(int x) {
	int len = 0;
	while (x > 0) {
		d[len++] = x % 10;
		x /= 10;
	}
	for (int i = len - 1; i >= 0; i--) {
		putchar('0' + d[i]);
	}
	if (len == 0) {
		putchar('0');
	}
	putchar('\n');
}

const int nax = 1e5+5;

struct DSU {
	int e[nax]; void init() { memset(e, -1, sizeof e); };
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

V<int> adj[nax];
int low[nax], disc[nax], t = 0;
bitset<nax> vis;

V<array<int, 2>> ans;

void dfs(int u, int p = -1) {
	vis[u] = 1;
	disc[u] = low[u] = t++;
	bool twi = 0;
	for(auto &v : adj[u]) if (v != p || twi) {
		if (vis[v]) low[u] = min(low[u], disc[v]);
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] > disc[u]) {
				cout << u + 1 << " " << v + 1 << endl;
			}
		}
	} else twi = 1;
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	memset(low, -1, sizeof low);
	memset(disc, -1, sizeof disc);
	vis.reset();

	int N = read(), M = read();
	DSU F, S; F.init(), S.init();

	int u, v;
	for(int e = 0; e < M; e++) {
		u = read() - 1, v = read() - 1;
		if (F.unite(u, v) || S.unite(u, v)) {
			// cout << u << " " << v << endl;
			adj[u].pb(v);
			adj[v].pb(u);
		}
	}

	for(int i = 0; i < N; i++) if (!vis[i]) dfs(i);

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4520 KB Output is correct
2 Correct 25 ms 4308 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5076 KB Output is correct
2 Correct 45 ms 4624 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6468 KB Output is correct
2 Correct 68 ms 6120 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 11024 KB Output is correct
2 Correct 96 ms 7556 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 12104 KB Output is correct
2 Correct 154 ms 9148 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 13992 KB Output is correct
2 Correct 196 ms 9020 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 13988 KB Output is correct
2 Correct 238 ms 9028 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 13400 KB Output is correct
2 Correct 304 ms 10556 KB Output is correct