답안 #96879 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96879	2019-02-12T15:01:56 Z	Retro3014	Pipes (CEOI15_pipes)	C++17	70 / 100	2887 ms	12136 KB

pipes

#include <stdio.h>
#include <vector>
#include <deque>
 
using namespace std;
#define MAX_N 80000
#define LN 17
typedef pair<int, int> pii;
 
int N, M;
vector<pii > gp[MAX_N+1];
int num[MAX_N+1];
int p[MAX_N+1][LN];
int up[MAX_N+1];
int lv[MAX_N+1];
pii edge[MAX_N+1];
int sz = 0;
int a, b, k, tmp, t, A, B, x;
 
 
 
void dfs(int x){
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i].first==p[x][0])	continue;
		dfs(gp[x][i].first);
		if(up[gp[x][i].first]<=lv[x])	edge[gp[x][i].second].first = edge[gp[x][i].second].second = 0;
		up[x] = min(up[x], up[gp[x][i].first]);
	}
}

deque<int> dq;

void init_graph(int x){
	
}
 
 
 
int main(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++)	num[i] = 1;
	for(int i=1; i<=N; i++)	lv[i] = up[i] = 1;
	while(M--){
		scanf("%d%d", &a, &b);
		A = a; B = b;
		for(int i=LN-1; i>=0; i--){
			if(p[A][i]!=0)	A = p[A][i];
			if(p[B][i]!=0)	B = p[B][i];
		}
		if(A==B){	A = a; B = b;
			for(int i=LN-1; i>=0; i--){
				if(lv[p[A][i]]>=lv[B])	A = p[A][i];
				if(lv[p[B][i]]>=lv[A])	B = p[B][i];
			}
			for(int i=LN-1; i>=0; i--){
				if(p[A][i]!=p[B][i]){
					A = p[A][i]; B = p[B][i];
				}
			}
			if(A!=B)	A = p[A][0];
			k = A;	up[a] = min(up[a], lv[k]);	up[b] = min(up[b], lv[k]);
		}else{
			if(num[A]>=num[B]){
				tmp = a; a = b; b = tmp;
				tmp = A; A = B; B = tmp;
			}
			num[B] += num[A];
			dfs(A);
			for(int i=1; i<LN; i++)	p[a][i] = 0;
			p[a][0] = b;
			lv[a] = lv[b]+1;
			gp[a].push_back({b, sz});	gp[b].push_back({a, sz});
			dq.push_back(a);
			while(!dq.empty()){
				x = dq.front(); dq.pop_front();
				up[x] = lv[x];
				for(int i=1; i<LN; i++)		p[x][i] = p[p[x][i-1]][i-1];
				for(int i=0; i<gp[x].size(); i++){
					if(gp[x][i].first==p[x][0])	continue;
					lv[gp[x][i].first] = lv[x]+1;
					p[gp[x][i].first][0] = x;
					dq.push_back(gp[x][i].first);
				}
			}
			edge[sz] = {a, b};	sz++;
		}
	}
	for(int i=1; i<=N; i++){
		int k = i;
		for(int j=LN-1; j>=0; j--){
			if(p[k][j]!=0)	k = p[k][j];
		}
		if(k==i)	dfs(k);
	}
	for(int i=0; i<sz; i++){
		if(edge[i].first!=0 && edge[i].second!=0)	printf("%d %d\n", edge[i].first, edge[i].second);
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gp[x].size(); i++){
                  ~^~~~~~~~~~~~~
pipes.cpp:40: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:44: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	4 ms	2176 KB	Output is correct
2	Correct	3 ms	2176 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	8 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	7 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	7 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-