oj.uz

답안 #34501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34501 2017-11-11T20:41:10 Z mohammad_kilani Pipes (CEOI15_pipes) C++14
90 / 100
 4721 ms 14676 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000007
#define oo 2000000000
const int N = 100010  , LOGN = 19;
bitset< N > bridge;
int dp[LOGN][N] , prnt[N] , num[N] , cur[N] , depth[N];
vector< pair<int,int> > t[N];

int find(int a){
	return (a == prnt[a] ? a : prnt[a] = find(prnt[a]));
}

int DFS(int node,int prnt){
	int sum = 0 , s = 0;
	for(int i=0;i<t[node].size();i++){
		if(t[node][i].first == prnt) continue;
		s = DFS(t[node][i].first,node);
		if(s > 0) bridge[t[node][i].second] = false;
		sum += s;
	}
	sum+= cur[node];
	cur[node] = 0 ;
	return sum;
}

void DFS2(int node,int pr,int pr2,int d){
	dp[0][node] = pr;
	depth[node] = d;
	for(int j=1;(1 << j) <= num[pr2];j++){
		if(dp[j-1][node] == -1)
			dp[j][node] = -1; 
		else 
			dp[j][node] = dp[j-1][dp[j-1][node]];
	}
	prnt[node] = pr2;
	for(int i=0;i<t[node].size();i++){
		if(t[node][i].first == pr) continue;
		DFS2(t[node][i].first,node,pr2,d+1);
	}
}

int lca(int u,int v){
	if(depth[u] > depth[v]) swap(u,v);
	for(int i=LOGN-1;i>=0;i--){
		if(depth[u] + (1 << i) <= depth[v]) v = dp[i][v] ;
	}
	if(u == v) return u;
	for(int i=LOGN-1;i>=0;i--){
		if(dp[i][u] != dp[i][v]){
			u = dp[i][u];
			v = dp[i][v];
		}
	}
	return dp[0][u];
}
 
int main() {
	//freopen("in.txt","r",stdin);
	int n , m , cnt = 0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		prnt[i] = i;
		dp[0][i] = -1;
		num[i] = 1;
	}
	int u , v;
	for(int i=0;i<m;i++){
		scanf("%d%d",&u,&v);
		int a= find(u);
		int b= find(v);
		if(a == b){
			cur[v]++;
			cur[u]++;
			cur[lca(u,v)]-=2;
		}
		else{
			bridge[cnt] = true;
			if(num[a] >= num[b]){
				DFS(b,-1);
				t[u].push_back(make_pair(v,cnt));
				t[v].push_back(make_pair(u,cnt++));
				num[a] += num[b];
				num[b] = 0 ;
				DFS2(v,u,a,depth[u] + 1);
			}
			else{
				DFS(a,-1);
				t[u].push_back(make_pair(v,cnt));
				t[v].push_back(make_pair(u,cnt++));
				num[b] += num[a];
				num[a] = 0 ;
				DFS2(u,v,b,depth[v] + 1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(prnt[i] == i){
			DFS(i,-1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<t[i].size();j++){
			if(i > t[i][j].first) continue;
			if(bridge[t[i][j].second]){
				printf("%d %d\n",i,t[i][j].first);
			}
		}
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int DFS(int, int)':
pipes.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[node].size();i++){
              ~^~~~~~~~~~~~~~~
pipes.cpp: In function 'void DFS2(int, int, int, int)':
pipes.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[node].size();i++){
              ~^~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<t[i].size();j++){
               ~^~~~~~~~~~~~
pipes.cpp:61: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3200 KB Output is correct
2 Incorrect 6 ms 3200 KB Wrong number of edges

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 3068 KB Output is correct
2 Correct 206 ms 3200 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 3832 KB Output is correct
2 Correct 500 ms 3788 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 720 ms 5404 KB Output is correct
2 Correct 605 ms 6008 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1275 ms 11072 KB Output is correct
2 Correct 1093 ms 11000 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2211 ms 12296 KB Output is correct
2 Correct 1809 ms 12004 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3190 ms 14504 KB Output is correct
2 Correct 3143 ms 14676 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3955 ms 14508 KB Output is correct
2 Correct 3970 ms 14468 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4721 ms 14004 KB Output is correct
2 Correct 3727 ms 14444 KB Output is correct