oj.uz

답안 #669499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669499 2022-12-06T14:57:01 Z Parsa_Fallahpour Pipes (CEOI15_pipes) C++17
0 / 100
 1000 ms 16476 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<pair<ll, ll>> G1[N];
vector<pair<ll, ll>> E;

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)
{
	seen[v] = 1;
	
	for(auto p: G1[v])
	{
		ll u = p.F, e = p.S;
		
		if(!seen[u])
		{
			H[u] = H[v] + 1;
			BE[u] = H[u];
			
			dfs(u);
			BE[v] = min(BE[v], BE[u]);
			
			//cout << BE[u] << SEP << H[u] << endl;
			
			if(BE[u] < H[u]) ans[e] = 1;
		}
		else
		{
			if(H[v] <= H[u]+1) continue;
			BE[v] = min(BE[v], H[u]);
			if(H[v] > H[u] + 1)ans[e] = 1;
		}
	}
	
}

/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ------------------------------------------------------------------------------SOLVE-----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/

void solve()
{
	Im_fucking_tired();
	
	cin >> n >> m;
	
	ll cnt = 0;
	for(int i=1; i<=m; i++, cnt++)
	{
		cin >> x >> y;
		
		if(getPar(x) != getPar(y))
		{
			Union(x, y);
			
			G1[y].PB({x, cnt});
			G1[x].PB({y, cnt});
			
			E.PB({min(x, y), max(x, y)});
		}
		else if(getPar2(x) != getPar2(y))
		{
			Union2(x, y);
			
			G1[y].PB({x, cnt});
			G1[x].PB({y, cnt});
			
			E.PB({min(x, y), max(x, y)});
		}
		else
		{
			cnt--;
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!seen[i]) H[i] = 1, dfs(i);
	}
	
	//cout << H[9] << SEP << H[10] << SEP << BE[9] << SEP << BE[10] << endl;
	
	vector<pair<ll, ll>> anss;
	
	for(int i=0; i<cnt; i++)
	{
		if(ans[i] == 0)
		{
			anss.PB(E[i]);
		}
	}
	
	sort(ALL(anss));
	
	if(anss.size() == 1 or anss[0] != anss[1]) cout << anss[0].F << SEP << anss[0].S << endl;
	for(int i=1; i<int(anss.size())-1; i++)
	{
		if(anss[i] != anss[i-1] && anss[i] != anss[i+1]) cout << anss[i].F << SEP << anss[i].S << endl;
	}
	if(anss.size() != 1 and anss[anss.size()-1] != anss[anss.size()-2]) cout << anss[anss.size()-1].F << SEP << anss[anss.size()-1].S << endl;
}

/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** -------------------------------------------------------------------------------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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 236 ms 13216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 790 ms 16476 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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