oj.uz

답안 #379808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379808 2021-03-19T10:55:59 Z soroush Pipes (CEOI15_pipes) C++17
20 / 100
 1443 ms 13420 KB 
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

vector < int > par1(maxn) , par2(maxn);
vector < int > adj[maxn];
int n , m;

int getpar(int v , vector < 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);
}

void dfs(int v , int p = 0 , int h = 1){
	par1[v] = par2[v] = h;	
	for(auto u : adj[v])if(u^p){
		if(!par2[u])
			dfs(u , v , h + 1) , par1[v] = min(par1[v] , par1[u]);
		else
			par1[v] = min(par1[v] , par2[u]);
	}
	if(par1[v] == h and h > 1)
		cout << v << ' ' << p << endl;
}

int32_t main(){
	migmig;
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++){
		int u , v;
		cin >> u >> v;
		merge(u , v);
	}
	fill(par2.begin() , par2.end() , 0);
	for(int i = 1 ; i <= n ; i ++)if(!par2[i])dfs(i);
	return(0);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 5880 KB Output is correct
2 Correct 325 ms 5484 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 10384 KB Output is correct
2 Incorrect 472 ms 6892 KB Wrong number of edges

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 13420 KB Output is correct
2 Incorrect 899 ms 8428 KB Wrong number of edges

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1232 ms 13300 KB Output is correct
2 Incorrect 1127 ms 8428 KB Wrong number of edges

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1426 ms 12748 KB Output is correct
2 Correct 1443 ms 9804 KB Output is correct