oj.uz

답안 #54785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54785 2018-07-05T05:30:24 Z 1등은 나의 것^^(#2059) Pipes (CEOI15_pipes) C++11
100 / 100
 1527 ms 8600 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int N = 100005, L = 17;

int n, m, p[3][N], par[N], dep[N];
bool vis[N], head[N];

vector<int> adj[N];
vector<pii> edg;

int Find (int T, int I) {
	if(p[T][I] == I) return I;
	return p[T][I] = Find(T, p[T][I]);
}

void calc (int C, int P) {
	vis[C] = true;
	par[C] = P;
	dep[C] = dep[P] + 1;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		p[0][i] = p[1][i] = p[2][i] = i;
	}
	for(int i=1;i<=m;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		if(Find(0, A) != Find(0, B)) {
			p[0][Find(0, A)] = B;
			adj[A].push_back(B);
			adj[B].push_back(A);
		}
		else if(Find(1, A) != Find(1, B)) {
			p[1][Find(1, A)] = B;
			edg.push_back({A, B});
		}
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			head[i] = true;
			calc(i, 0);
		}
	}
	for(auto &T : edg) {
		int A, B;
		tie(A, B) = T;
		while(true) {
			int X = Find(2, A);
			int Y = Find(2, B);
			if(X == Y) break;
			if(dep[X] < dep[Y]) swap(X, Y);
			p[2][X] = par[X];
		}
	}
	for(int i=1;i<=n;i++) {
		if(!head[i] && Find(2, i) == i) {
			printf("%d %d\n", i, par[i]);
		}
	}
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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