oj.uz

답안 #1035162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035162 2024-07-26T05:26:19 Z vjudge1 Pipes (CEOI15_pipes) C++14
50 / 100
 818 ms 65536 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3932 KB Output is correct
2 Correct 7 ms 3676 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 3676 KB Output is correct
2 Correct 66 ms 3676 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 4212 KB Output is correct
2 Correct 131 ms 3932 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 5536 KB Output is correct
2 Correct 170 ms 15956 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 9704 KB Output is correct
2 Runtime error 229 ms 24912 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 10544 KB Output is correct
2 Runtime error 377 ms 41300 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 527 ms 12272 KB Output is correct
2 Runtime error 510 ms 49160 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 643 ms 12168 KB Output is correct
2 Runtime error 625 ms 60396 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 792 ms 11696 KB Output is correct
2 Runtime error 818 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -