oj.uz

Submission #448657

# Submission time Handle Problem Language Result Execution time Memory
448657 2021-07-31T11:56:26 Z Millad Pipes (CEOI15_pipes) C++14
100 / 100
 1335 ms 13320 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3148 KB Output is correct
2 Correct 6 ms 2892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2964 KB Output is correct
2 Correct 126 ms 2836 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 3648 KB Output is correct
2 Correct 230 ms 3104 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 5188 KB Output is correct
2 Correct 278 ms 4808 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 10252 KB Output is correct
2 Correct 412 ms 6768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 11144 KB Output is correct
2 Correct 638 ms 8540 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 13276 KB Output is correct
2 Correct 848 ms 8384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 13320 KB Output is correct
2 Correct 1053 ms 8408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 12704 KB Output is correct
2 Correct 1259 ms 9892 KB Output is correct