oj.uz

Submission #54820

# Submission time Handle Problem Language Result Execution time Memory
54820 2018-07-05T07:32:19 Z 나는야 테스트(#2061) Pipes (CEOI15_pipes) C++11
100 / 100
 1445 ms 8624 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int N = 100005;

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2944 KB Output is correct
2 Correct 8 ms 2972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3036 KB Output is correct
2 Correct 110 ms 2936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 3296 KB Output is correct
2 Correct 236 ms 3320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 4080 KB Output is correct
2 Correct 302 ms 4348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 6864 KB Output is correct
2 Correct 438 ms 6928 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 7532 KB Output is correct
2 Correct 722 ms 7148 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 8624 KB Output is correct
2 Correct 959 ms 8588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1237 ms 8584 KB Output is correct
2 Correct 1187 ms 8592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 8316 KB Output is correct
2 Correct 1445 ms 8232 KB Output is correct