Submission #448655

#	Time	Username	Problem	Language	Result	Execution time	Memory
448655		Millad	Pipes (CEOI15_pipes)	C++14	40 / 100	1394 ms	49868 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 long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
ll n, m, par[maxn], p2[maxn], sz[maxn], s2[maxn], h[maxn], mn[maxn];
vector <ll> adj[maxn];
bool mrk[maxn];
ll get_par(ll v){
	if(par[v] == v)return v;
	par[v] = get_par(par[v]);
	return par[v];
}
bool merge(ll v, ll u){
	u = get_par(u);
	v = get_par(v);
	if(u == v)return 0;
       	if(sz[u] < sz[v])swap(u, v);
	sz[u] += v;
	par[v] = u;
	return 1;
}
ll get_p2(ll v){
        if(p2[v] == v)return v;
        p2[v] = get_p2(p2[v]);
        return p2[v];
}
bool merge2(ll v, ll u){
        u = get_p2(u);
        v = get_p2(v);
        if(u == v)return 0;
        if(s2[u] < s2[v])swap(u, v);
        s2[u] += v;
        p2[v] = u;
	return 1;
}
void dfs(ll v){
	mrk[v] = 1;
	bool b = 0;
	mn[v] = h[v];
	for(ll j : adj[v]){
		if(mrk[j]){
			if(j == par[v]){
				if(!b)b = 1;
				else mn[v] = min(mn[v], h[j]);	
			}
			else mn[v] = min(mn[v], h[j]);
			continue;
		}
		h[j] = h[v] + 1;
		par[j] = v;
		dfs(j);
		mn[v] = min(mn[v], mn[j]);
	}
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(ll i = 1; i <= n; i ++){
		par[i] = i;
		p2[i] = i;
		sz[i] = 1;
		s2[i] = 1;
	}
	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 ++)par[i] = 0;
	for(ll i = 1; i <= n; i ++){
		if(!mrk[i])dfs(i);
		if(mn[i] == h[i] && (par[i])){
			cout << i << ' ' << par[i] << '\n';
		}
	}
}
 

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