oj.uz

답안 #379891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379891 2021-03-19T15:51:03 Z soroush Pipes (CEOI15_pipes) C++17
0 / 100
 1370 ms 14132 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e5 + 1;
 
#define pb push_back
#define endl '\n'
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
 
int par1[maxn] , par2[maxn];
vector < int > adj[maxn];
int n , m;
 
int getpar(int v , int *par){
	return((par[v]) ? par[v] = getpar(par[v] , par) : v);
}
 
void merge(int v , int u){
	if(getpar(u , par1) ^ getpar(v , par1))
		par1[getpar(u , par1)] = getpar(v , par1);
	else if(getpar(u , par2) ^ getpar(v , par2))
		par2[getpar(u , par2)] = getpar(v , par2);
	else
		return;
	adj[u].pb(v);
	adj[v].pb(u);
}
 
int par[maxn] , h[maxn] , cnt[maxn];
 
void dfs(int v){
  	h[v] = h[par[v]] + 1;
	par1[v] = par2[v] = h[v];	
	for(auto u : adj[v])if(u^par[v]){
		if(!par2[u])
			par[u] = v , dfs(u) , par1[v] = min(par1[v] , par1[u]);
		else
			par1[v] = min(par1[v] , par2[u]);
	}else cnt[v];
	if(par1[v] == h[v] and par[v] and cnt[v] == 1)
		cout << v << ' ' << par[v] << endl;
}
 
int32_t main(){
	migmig;
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++){
		int u , v;
		cin >> u >> v;
		merge(u , v);
	}
	for(int i = 1 ; i <= n ; i ++)par2[i] = 0;
	for(int i = 1 ; i <= n ; i ++)if(!par2[i])dfs(i);
	return(0);
}

Compilation message

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:40:13: warning: statement has no effect [-Wunused-value]
   40 |  }else cnt[v];
      |        ~~~~~^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3180 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 3052 KB Output is correct
2 Incorrect 123 ms 2924 KB Wrong number of edges

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 3820 KB Output is correct
2 Incorrect 225 ms 3340 KB Wrong number of edges

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 5356 KB Output is correct
2 Incorrect 333 ms 4972 KB Wrong number of edges

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 494 ms 10688 KB Output is correct
2 Incorrect 409 ms 7148 KB Wrong number of edges

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 707 ms 11884 KB Output is correct
2 Incorrect 712 ms 9068 KB Wrong number of edges

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 973 ms 14092 KB Output is correct
2 Incorrect 891 ms 9220 KB Wrong number of edges

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1148 ms 14132 KB Output is correct
2 Incorrect 1080 ms 9068 KB Wrong number of edges

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1361 ms 13552 KB Output is correct
2 Incorrect 1370 ms 10548 KB Wrong number of edges