oj.uz

답안 #669542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669542 2022-12-06T17:17:37 Z Parsa_Fallahpour Pipes (CEOI15_pipes) C++17
100 / 100
 958 ms 14996 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define TOF_IO                                   ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y)	                         freopen(x, "r", stdin); freopen(y, "w", stdout);
#define SEP                                      ' '
#define endl                                     '\n'
#define Set_Prec(k, x)	                         cout << fixed << setprecision(k) << x << '\n';
#define BSearch(first, second, t)                lower_bound(arr, arr+n, t)-arr
#define F                                        first
#define S                                        second
#define ALL(x)                                   (x).begin(), (x).end()
#define PB                                       push_back
#define EDGE(arr, x, y)                          arr[x].PB(y), arr[y].PB(x)
 
typedef int ll; 
typedef long double lld;
 
const ll M = 1e9+7;
//const ll IM = 1e18 + 37;
 
//ll POW(ll a, ll b, ll md); ll GCD(ll a, ll b); ll LCM(ll a, ll b); int lis(std::vector<int>& v);
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
 
void InverseofNumber(ll p = M); void InverseofFactorial(ll p = M); void factorial(ll p = M); ll nPr(ll N, ll R, ll p = M); ll nCr(ll N, ll R, ll p = M); void comb();
*/
 
const ll N = 1e5 + 10;
 
ll n, m, x, y, z, par[N], H[N], BE[N], par2[N];
 
bool seen[N], ans[N];
 
vector<ll> G1[N];
 
ll getPar(ll v)
{
	return (par[v] == v? v : par[v] = getPar(par[v]));
}
ll getPar2(ll v)
{
	return (par2[v] == v? v : par2[v] = getPar2(par2[v]));
}
 
void Union(ll v, ll u)
{
	v = getPar(v); u = getPar(u);
	par[v] = u;
}
void Union2(ll v, ll u)
{
	v = getPar2(v); u = getPar2(u);
	par2[v] = u;
}
 
void Im_fucking_tired()
{
	for(int i=0; i<N; i++)
	{
		par[i] = i;
		par2[i] = i;
	}
}
 
void dfs(ll v, ll fad)
{
	seen[v] = 1;
	
	for(auto u: G1[v])
	{
		if(!seen[u])
		{
			H[u] = H[v] + 1;
			BE[u] = H[u];
			
			dfs(u, v);
			BE[v] = min(BE[v], BE[u]);
			
			//cout << BE[u] << SEP << H[u] << endl;
			
			if(BE[u] < H[u]) continue;
			
			if(count(ALL(G1[v]), u) == 1) cout << v << SEP << u << endl;
		}
		else
		{
			if(u == fad)
			{
				continue;
			}
			BE[v] = min(BE[v], H[u]);
		}
	}
	
}
 
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ------------------------------------------------------------------------------SOLVE-----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
 
void solve()
{
	Im_fucking_tired();
	
	cin >> n >> m;
	
	ll cnt = 0;
	for(int i=1; i<=m; i++, cnt++)
	{
		cin >> x >> y;
		if(x > y) swap(x, y);
		
		if(getPar(x) != getPar(y))
		{
			Union(x, y);
			
			EDGE(G1, x, y);
		}
		else if(getPar2(x) != getPar2(y))
		{
			Union2(x, y);
			
			EDGE(G1, x, y);
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!seen[i]) H[i] = 1, dfs(i, -1);
	}
	
}
 
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** -------------------------------------------------------------------------------MAIN-----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
 
int main()
{
	//File_IO("input.txt", "output.txt");
	TOF_IO;
 
	ll t=1;
	//cin >> t;
	
	for(int k=0; k<t; k++)
	{
		solve();
	}
	
	return 0;
}
 
 
 
 
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ---------------------------------------------------------------------------FUNCTIONS----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0};int ans = ((fact[N] * factI[R]) % p * factI[N - R]) % p;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * POW(a * a % md, b / 2, md) % md : POW(a * a % md, b / 2, md) % md));}
//ll GCD(ll a, ll b) {return b?GCD(b,a%b):a;}
//ll LCM(ll a, ll b) {return a/GCD(a,b)*b;}
 
//int lis(std::vector<int>& v){if (v.size() == 0) {return 0;} vector<int> tail(v.size(), 0); int length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3924 KB Output is correct
2 Correct 5 ms 3636 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 3848 KB Output is correct
2 Correct 79 ms 3588 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 4472 KB Output is correct
2 Correct 159 ms 3960 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 6220 KB Output is correct
2 Correct 195 ms 5704 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 11552 KB Output is correct
2 Correct 282 ms 7508 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 494 ms 12832 KB Output is correct
2 Correct 472 ms 9520 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 669 ms 14992 KB Output is correct
2 Correct 621 ms 9260 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 805 ms 14996 KB Output is correct
2 Correct 752 ms 9304 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 958 ms 14404 KB Output is correct
2 Correct 922 ms 11224 KB Output is correct