답안 #54799 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54799	2018-07-05T05:51:34 Z	윤교준(#1510)	Pipes (CEOI15_pipes)	C++11	100 / 100	4502 ms	11384 KB

pipes

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int GE[100001], GD[300005], GI[300005], Gn = 100001;

int prt[100001][17], dep[100001];
int ud[100001], cnt[2][100001];
bitset<100001> chk;

int N, M;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 0; i < 17; i++) if(dt & (1<<i))
		b = prt[b][i];
	if(a == b) return a;
	for(int i = 16; ~i; i--) if(prt[a][i] != prt[b][i]) {
		a = prt[a][i]; b = prt[b][i];
	}
	return prt[a][0];
}

void f(int i) {
	for(int gi = i, v;;) {
		v = GD[gi];
		if(!v || !gi || gi == GE[i]) break;
		if(!dep[v]) {
            prt[v][0] = i;
            dep[v] = dep[i] + 1;
            f(v);
		}
		gi = GI[gi];
	}
}
void g(int i) {
	for(int gi = i, v;;) {
		v = GD[gi];
		if(!v || !gi || gi == GE[i]) break;
		if(dep[i] < dep[v]) {
            g(v);
            cnt[1][i] += cnt[1][v];
		}
		gi = GI[gi];
	}
    cnt[1][i] -= cnt[0][i];
    chk[i] = !!cnt[1][i];
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> N >> M;
	iota(ud, ud+N+1, 0);
	iota(GE, GE+N+1, 0);

	for(int i = 0, a, b; i < M; i++) {
		cin >> a >> b;
		if(uf(a) == uf(b)) continue;
		uf(a, b);
		{
			GD[GE[a]] = b;
			GI[GE[a]] = Gn;
			GE[a] = Gn;
			Gn++;
		}
		{
			GD[GE[b]] = a;
			GI[GE[b]] = Gn;
			GE[b] = Gn;
			Gn++;
		}
	}

	for(int i = 1; i <= N; i++) {
		if(dep[i]) continue;
		dep[i] = 1;
		f(i);
	}

	for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++)
		prt[i][j] = prt[prt[i][j-1]][j-1];

	cin.seekg(0, std::ios::beg);

	cin >> N >> M;
	for(int i = 0, a, b, c; i < M; i++) {
		cin >> a >> b;
		if(dep[a] > dep[b]) swap(a, b);
		if(prt[b][0] == a && !chk[b]) {
			chk[b] = true;
			continue;
		}
		c = lca(a, b);
		if(a == c) {
			cnt[0][a]++;
			cnt[1][b]++;
		} else {
			cnt[0][c] += 2;
			cnt[1][a]++;
			cnt[1][b]++;
		}
	}

	chk.reset();

	for(int i = 1; i <= N; i++) if(1 == dep[i]) g(i);
	for(int i = 1; i <= N; i++) if(1 < dep[i] && !chk[i])
		printf("%d %d\n", i, prt[i][0]);
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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

답안 #54799

Compilation message