oj.uz

답안 #81980

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81980 2018-10-28T09:45:42 Z Saboon Pipes (CEOI15_pipes) C++14
40 / 100
 738 ms 1172 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 block = 320;

int h[maxn], par[maxn], parsqrt[maxn], dp[maxn];
bool cut[maxn];

int lca (int v, int u) {
	if (h[v] < h[u])
		swap (v, u);
	while (h[v] > h[u]) {
		if (h[v] - block >= h[u])
			v = parsqrt[v];
		else
			v = par[v];
	}
	if (v == u)
		return v;
	while (v != u) {
		if (parsqrt[v] != parsqrt[u]) {
			v = parsqrt[v];
			u = parsqrt[u];
		}
		else {
			v = par[v];
			u = par[u];
		}
	}
	return v;
}

vector <int> g[maxn];

void dfs2 (int v, int p) {
	dp[v] = h[v];
	for (auto w : g[v]) {
		if (w != p) {
			h[w] = h[v] + 1;
			dfs2 (w, v);
		}
	}
}

void dfs1 (int v, int p) {
	par[v] = p;
	parsqrt[v] = p;
	for (int i = 1; i < block; i++)
		parsqrt[v] = par[parsqrt[v]];

	for (auto u : g[v]) {
		if (u != p) {
			dfs1 (u, v);
		if (h[v] > h[u])
			cut[u] = cut[v];
		}
	}
}

void dfs (int v, int p = -1) {
	for (auto w : g[v]) {
		if (w != p) {
			dfs (w, v);
			dp[v] = min (dp[v], dp[w]);
		}
	}
	cut[v] &= (h[v] <= dp[v]);
}

int dpar[maxn];
int get_par (int v) {
	if (dpar[v] < 0)
		return v;
	return dpar[v] = get_par (dpar[v]);
}

int n;
void merge (int v, int u) {
	int vpar = get_par (v), upar = get_par (u);
	dfs (vpar);
	dfs1 (v, u);
	cut[v] = 1;
	h[v] = h[u] + 1;
	dfs2 (v, u);
	dpar[upar] += dpar[vpar];
	dpar[vpar] = upar;
	g[u].PB (v);
	g[v].PB (u);
}		

int main() {
	memset (par, -1, sizeof par);
	memset (dpar, -1, sizeof dpar);
	int m;
	cin >> n >> m;
	while (m --) {
		int v, u;
		cin >> v >> u;
		int vpar = get_par(v), upar = get_par(u);
		if (vpar != upar) {
			if (dpar[vpar] < dpar[upar])
				swap (v, u);
			merge (v, u);
		}
		else {
			int w = lca (v, u);
			dp[v] = min (dp[v], h[w]);
			dp[u] = min (dp[u], h[w]);
		}
	}
	
	for (int i = 1; i <= n; i++)
		if (dpar[i] < 0)
			dfs (i);
	
	
	for (int i = 1; i <= n; i++)
		if (cut[i])
			cout << i << " " << par[i] << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -