oj.uz

Submission #230128

# Submission time Handle Problem Language Result Execution time Memory
230128 2020-05-08T16:30:44 Z Atalasion Pipes (CEOI15_pipes) C++14
0 / 100
 1912 ms 65536 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, m, sz[2][N], par[2][N], mn[N], h[N];
vi G[N];
bool mark[N];

int getpar(int ind, int v){
	return (par[ind][v] == v?v:par[ind][v] = getpar(ind, par[ind][v]));
}

void merge(int v, int u, int id){
	int V = v, U = u;
	int vv = getpar(0, v), uu = getpar(0, u);
	if (sz[0][vv] < sz[0][uu]) swap(vv, uu);
	if (vv == uu){
		v = getpar(1, v), u = getpar(1, u);
		if (v != u){
			if (sz[1][v] < sz[1][u]) swap(v, u);
			par[1][u] = v;
			sz[1][v] += sz[1][u];
			G[V].pb(U);
			G[U].pb(V);
		//	cout << V << ' ' << U << '\n';
		}
		return;
	}
	par[0][uu] = vv;
	sz[0][vv] += sz[0][uu];
	G[u].pb(v), G[v].pb(u);
	// << v << ' ' << u << '\n';
	return;
}

void DFS(int v, int p = 0){
	mark[v] = 1;
	mn[v] = h[v];
	//cout << v << '\n';
	for (auto u:G[v]){
		if (u == p) continue;
		if (!mark[u]){
			h[u] = h[v] + 1;
			DFS(u, v);
			mn[v] = min(mn[v], mn[u]);
			if (mn[u] > h[v]){
				printf("%d %d\n", min(u, v), max(u, v));
				//int aa;
			}
		}else if(h[u] < h[v]){
			mn[v] = min(mn[v], h[u]);
		}
	}
	//cout << "Fuck " << v << ' ' << mn[v] << '\n';
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < N; i++) par[0][i] = par[1][i] = i, sz[0][i] = sz[1][i] = 1; 
	for (int i = 1; i <= m; i++){
		int v, u;
		scanf("%d %d", &v, &u);
		merge(v, u, i);
	}
	for (int i = 1; i <= n; i++) if (!mark[i]) DFS(i);
	










	return 0;
}

/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/

Compilation message

pipes.cpp: In function 'int32_t main()':
pipes.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8192 KB Output is correct
2 Incorrect 9 ms 8192 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8704 KB Output is correct
2 Incorrect 14 ms 8576 KB Wrong number of edges

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 14088 KB Output is correct
2 Incorrect 174 ms 13816 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 18808 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 478 ms 27016 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 629 ms 35756 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 923 ms 49252 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1237 ms 61932 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1557 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1912 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -