oj.uz

답안 #1034721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034721 2024-07-25T17:10:06 Z vjudge1 Pipes (CEOI15_pipes) C++17
40 / 100
 666 ms 56740 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>;
 
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]);
			// cout << u << " " << low[u] << " " << disc[v] << endl;
			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, M; cin >> N >> M;
	DSU F, S; F.init(), S.init();
 
	int u, v;
	for(int e = 0; e < M; e++) {
		cin >> u >> v; --u, --v;
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 7680 KB Output is correct
2 Correct 63 ms 7176 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 10236 KB Output is correct
2 Correct 121 ms 10624 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 14932 KB Output is correct
2 Runtime error 136 ms 20048 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 255 ms 21924 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 377 ms 29368 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 447 ms 36520 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 567 ms 44012 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 666 ms 56740 KB Memory limit exceeded
2 Halted 0 ms 0 KB -