oj.uz

Submission #54782

# Submission time Handle Problem Language Result Execution time Memory
54782 2018-07-05T05:16:44 Z 1등은 나의 것^^(#2059) Pipes (CEOI15_pipes) C++11
100 / 100
 1619 ms 14968 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 100005, L = 17;

int n, m, p[2][N], par[L][N], dep[N], sum[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) {
	par[0][C] = P;
	vis[C] = true;
	dep[C] = dep[P] + 1;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}

int getlca (int A, int B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(int i=L;i--;) {
		if((1<<i) <= dep[A] - dep[B]) {
			A = par[i][A];
		}
	}
	if(A == B) return A;
	for(int i=L;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A];
			B = par[i][B];
		}
	}
	return par[0][A];
}

void getsum (int C, int P) {
	for(auto &T : adj[C]) {
		if(T == P) continue;
		getsum(T, C);
		sum[C] += sum[T];
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		p[0][i] = p[1][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(int k=1;k<L;k++) {
		for(int i=1;i<=n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
	for(auto &T : edg) {
		sum[T.X]++;
		sum[T.Y]++;
		sum[getlca(T.X, T.Y)] -= 2;
	}
	getsum(1, 0);
	for(int i=1;i<=n;i++) {
		if(!head[i] && !sum[i]) printf("%d %d\n", i, par[0][i]);
	}
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:57: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:63: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 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 3192 KB Output is correct
2 Correct 115 ms 3164 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 4028 KB Output is correct
2 Correct 239 ms 4060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 5644 KB Output is correct
2 Correct 288 ms 6228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 11308 KB Output is correct
2 Correct 444 ms 11276 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 12548 KB Output is correct
2 Correct 731 ms 12164 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 14836 KB Output is correct
2 Correct 950 ms 14908 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 14840 KB Output is correct
2 Correct 1212 ms 14968 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1619 ms 14216 KB Output is correct
2 Correct 1479 ms 14688 KB Output is correct