Submission #448657

#	Time	Username	Problem	Language	Result	Execution time	Memory
448657		Millad	Pipes (CEOI15_pipes)	C++14	100 / 100	1335 ms	13320 KiB

pipes

//In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll n, m, a[maxn], b[maxn];
vector <ll> adj[maxn];
bool mrk[maxn];
ll get_a(ll v){
	if(a[v] == v)return v;
	a[v] = get_a(a[v]);
	return a[v];
}
bool merge(ll v, ll u){
	u = get_a(u);
	v = get_a(v);
	if(u == v)return 0;
	a[v] = u;
	return 1;
}
ll get_b(ll v){
        if(b[v] == v)return v;
        b[v] = get_b(b[v]);
        return b[v];
}
bool merge2(ll v, ll u){
        u = get_b(u);
        v = get_b(v);
        if(u == v)return 0;
        b[v] = u;
	return 1;
}
vector <pll> vec;
void dfs(ll v, ll p){
	mrk[v] = 1;
	bool bl = 0;
	b[v] = a[v];
	for(ll j : adj[v]){
		if(mrk[j]){
			if(j == p){
				if(!bl)bl = 1;
				else b[v] = min(b[v], a[j]);	
			}
			else b[v] = min(b[v], a[j]);
			continue;
		}
		a[j] = a[v] + 1;
		dfs(j, v);
		b[v] = min(b[v], b[j]);
	}
	if(a[v] == b[v] && p)vec.pb({v, p});
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(ll i = 1; i <= n; i ++){
		b[i] = i;
		a[i] = i;
	}
	for(ll i = 0; i < m; i ++){
		ll u, v; cin >> u >> v;
		if(merge(u, v)){
			adj[u].pb(v);
	                adj[v].pb(u);
			continue;
		}
		else if(merge2(u, v)){
			adj[u].pb(v);
                        adj[v].pb(u);
		}
	}
	for(ll i = 1; i <= n; i ++){
		a[i] = 0;
		b[i] = 0;
	}
	for(ll i = 1; i <= n; i ++){
		if(!mrk[i]){
			dfs(i, 0);
			continue;
		}
	}
	for(pll i : vec)cout << i.F << ' ' << i.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