oj.uz

Submission #448656

# Submission time Handle Problem Language Result Execution time Memory
448656 2021-07-31T11:46:36 Z Millad Pipes (CEOI15_pipes) C++14
50 / 100
 1337 ms 38472 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, par[maxn], p2[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;
	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;
        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;
	}
	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.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 3196 KB Output is correct
2 Correct 6 ms 3020 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 3160 KB Output is correct
2 Correct 116 ms 3020 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3848 KB Output is correct
2 Correct 235 ms 3532 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 5276 KB Output is correct
2 Runtime error 291 ms 18736 KB Memory limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 9936 KB Output is correct
2 Runtime error 407 ms 25244 KB Memory limit exceeded

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 11220 KB Output is correct
2 Correct 654 ms 16280 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 13268 KB Output is correct
2 Runtime error 867 ms 20380 KB Memory limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 13124 KB Output is correct
2 Runtime error 1075 ms 23844 KB Memory limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 12580 KB Output is correct
2 Runtime error 1303 ms 38472 KB Memory limit exceeded