oj.uz

Submission #86630

# Submission time Handle Problem Language Result Execution time Memory
86630 2018-11-27T04:11:21 Z arafat_01 Pipes (CEOI15_pipes) C++17
20 / 100
 1552 ms 65536 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll inf = 1e18 + 9;

inline void boost () {
	ios_base::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
}
int n, m;
vector < vector < int > > g;
vector < bool > used;
vector < int > tin, fup;
int timer;
map < pair < int , int >, int > cnt;
vector < pair < int, int > > ans;

void dfs (int v, int pr = 0) {
	used[v] = 1;
	tin[v] = fup[v] = ++ timer;
	for (auto to : g[v]) {
		if (to == pr) continue;
		if (used[to]) {
			fup[v] = min (fup[v], tin[to]);		
		} else {
			dfs (to, v);
			fup[v] = min (fup[v], fup[to]);
			if (fup[to] > tin[v] && cnt[mp (v, to)] <= 1) {
				ans.pb (mp (v, to));
			}
		}
	}

}

int main () {
 	boost ();
 	cin >> n >> m;
  int u, v;
  g.resize (n + 1);
  used.resize (n + 1);
  tin.resize (n + 1);
  fup.resize (n + 1);
	for (int i = 1;i <= m;i ++) {
		cin >> u >> v;
 		g[u].pb (v);
 		g[v].pb (u);
 		cnt[mp (u, v)] ++;
 		cnt[mp (v, u)] ++;
 	}
 	for (int i = 1;i <= n;i ++) {
 		if (!used[i]) dfs (i);
 	}
	for (auto it : ans) cout << it.F << ' ' << it.S << endl; 	 	

	return 0;                                                   	
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2432 KB Output is correct
2 Correct 15 ms 2176 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1386 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1408 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1366 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1406 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1552 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1409 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1428 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1465 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -