oj.uz

Submission #54786

# Submission time Handle Problem Language Result Execution time Memory
54786 2018-07-05T05:33:50 Z 1등은 나의 것^^(#2059) Pipes (CEOI15_pipes) C++11
100 / 100
 1456 ms 8684 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 4 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 3072 KB Output is correct
2 Correct 8 ms 3056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2936 KB Output is correct
2 Correct 117 ms 2916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 3300 KB Output is correct
2 Correct 239 ms 3288 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 4092 KB Output is correct
2 Correct 297 ms 4320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 6828 KB Output is correct
2 Correct 406 ms 6828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 7512 KB Output is correct
2 Correct 695 ms 7212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 8580 KB Output is correct
2 Correct 994 ms 8684 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 8560 KB Output is correct
2 Correct 1225 ms 8684 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 8316 KB Output is correct
2 Correct 1439 ms 8280 KB Output is correct