Submission #385505

#	Time	Username	Problem	Language	Result	Execution time	Memory
385505		MahdiBahramian	Pipes (CEOI15_pipes)	C++14	100 / 100	1317 ms	15628 KiB

pipes

#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define make make_pair
using namespace std;
const int Max = 1e5 + 10;

int par[Max][2];
vector<pair<int , int>> N[Max];
int h[Max];
vector<pair<int , int>> E;

int PAR(int a , int k)
{
	if(par[a][k] == a) return a;
	return par[a][k] = PAR(par[a][k] , k);
}
bool UNI(int a , int b , bool k)
{
	a = PAR(a , k);
	b = PAR(b , k);
	if(a == b) return 0;
	par[a][k] = b;
	return 1;
}
int DFS(int v , int e , int p)
{
	int mn = Max;
	for(pair<int , int> u : N[v])
		if(!h[u.F]) h[u.F] = h[v] + 1 , mn = min(DFS(u.F , u.S , v) , mn);
		else if(u.S != e) mn = min(mn , h[u.F]);
	if(mn >= h[v]) E.pb(make(p , v));
	return mn;
}
int main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int n , m; cin >> n >> m;
	for(int i = 1 ; i <= n ; i++) par[i][0] = par[i][1] = i;
	for(int i = 1 ; i <= m ; i++)
	{
		int a , b; cin >> a >> b;
		if(UNI(a , b , 0) || UNI(a , b , 1)) N[a].pb(make(b , i)) , N[b].pb(make(a , i));
	}
	for(int v = 1 ; v <= n ; v++)
		if(!h[v])
			h[v] = 1 , DFS(v , 0 , v);
	//cout << '\n';
	for(pair<int , int> e : E)
		if(e.F != e.S)cout << e.F << ' ' << e.S << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10