oj.uz

Submission #339319

# Submission time Handle Problem Language Result Execution time Memory
339319 2020-12-25T04:38:32 Z mario05092929 Pipes (CEOI15_pipes) C++11
0 / 100
 1371 ms 65536 KB 
#include <bits/stdc++.h>
#define x first
#define w second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pl;
typedef pair <ll,ll> pi;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int V,E,go,c[100005];
int p[100005],p2[100005];
vector <int> v[100005];
vector <pair<int,int>> ans;

int Find(int x) {return (x^p[x] ? p[x] = Find(p[x]) : x);}
int Find2(int x) {return (x^p2[x] ? p2[x] = Find2(p2[x]) : x);}

int dfs(int x,int la) {
	if(c[x]) return 0;
	c[x] = ++go;
	int ret = go;
	for(int i : v[x]) {
		if(i == la) continue;
		int tmp = dfs(i,x);
		if(tmp) ret = min(ret,tmp);
		else ret = min(ret,c[i]);
		if(tmp > c[x]) cout << x << ' ' << i << '\n';
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> V >> E;
	for(int i = 1;i <= V;i++) p[i] = p2[i] = i;
	for(int i = 1;i <= E;i++) {
		int x,y;
		cin >> x >> y;
		if(Find(x)^Find(y)) {
			p[p[y]] = p[x];
			v[x].pb(y), v[y].pb(x);
		}
		else if(Find2(x)^Find2(y)) {
			p2[p2[y]] = p2[x];
			v[x].pb(y), v[y].pb(x);
		}
	}
	for(int i = 1;i <= V;i++) if(!c[i]) dfs(i,-1);
}

Compilation message

pipes.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
pipes.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
pipes.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 13548 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 328 ms 21752 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 472 ms 31852 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 713 ms 45704 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 939 ms 58860 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1123 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1371 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -