Submission #669533

#	Time	Username	Problem	Language	Result	Execution time	Memory
669533		Parsa_Fallahpour	Pipes (CEOI15_pipes)	C++17	50 / 100	976 ms	15368 KiB

pipes

#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];

map<pair<ll, ll>, bool> flag;
 
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 && flag[{u, v}] == 0) 
			{
				flag[{u, v}] = 1;
				continue;
			}
			BE[v] = min(BE[v], H[u]);
			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)});
			ans[cnt] = 1;
		}
		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;
	
	for(int i=0; i<cnt; i++)
	{
		if(ans[i] == 0)
		{
			cout << E[i].F << SEP << E[i].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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10