oj.uz

Submission #1035163

# Submission time Handle Problem Language Result Execution time Memory
1035163 2024-07-26T05:26:49 Z vjudge1 Pipes (CEOI15_pipes) C++11
40 / 100
 970 ms 64860 KB 
#pragma GCC optimize("O3,unroll-loops")        
#include <iostream>
        #include <vector>
        using namespace std;
         
        const int N = 1e5+2;
        struct dsu {
        	int e[N];
        	int find(int &x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
        	bool join(int a, int b) {
        		a = find(a), b = find(b);
        		if (a == b) return false;
        		if (e[a] > e[b]) swap(a, b);
        		e[a] += e[b]; e[b] = a;
        		return true;
        	}
        } d1, d2;
        vector<int> g[N];
        int timer=0;
        void dfs(int at, int par) {
        	d1.e[at]=d2.e[at]=++timer;
        	for(int &to:g[at]) {
        		if(to == par) {
        			par+=N;
        			continue;
        		}
        		if(d2.e[to]) {
        			d1.e[at]=min(d1.e[at], d2.e[to]);		
        		} else {
        			dfs(to, at);
        			d1.e[at]=min(d1.e[at], d1.e[to]);
        		}
        	}
        	if(par>N)par-=N;
        	if(d1.e[at] == d2.e[at] and at!=par) {
        		printf("%d %d\n", at, par);
        	}
        }
        int n, m, u, v;
        int main() {
        	srand(time(0));
         
        	scanf("%d %d", &n, &m);
        	//nt u, v;
        	for(int i = 1;i<N;i++)d1.e[i]=d2.e[i]=-1;
        	for(int i = 0;i<m;i++) {
        		scanf("%d %d", &u, &v);
        		if((d1.join(u, v) || d2.join(u, v))) {
        			g[u].push_back(v);
        			g[v].push_back(u);
        		}
        	}
        	for(int i = 1;i<N;i++)d1.e[i]=d2.e[i]=0;
        	for(int i= 1;i<=n;i++) {
        		if(!d1.e[i]) {
        			dfs(i, i);
        		}
        	}
        }

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3928 KB Output is correct
2 Correct 4 ms 3748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8272 KB Output is correct
2 Correct 68 ms 8276 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12112 KB Output is correct
2 Correct 143 ms 13396 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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