oj.uz

답안 #1035158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035158 2024-07-26T05:24:40 Z vjudge1 Pipes (CEOI15_pipes) C++
40 / 100
 803 ms 47332 KB 
    	#pragma GCC optimize("O3,unroll-loops")
    	//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
     
    #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:45:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |          scanf("%d %d", &n, &m);
      |          ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:49:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |           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 5 ms 3932 KB Output is correct
2 Correct 4 ms 3676 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 14156 KB Output is correct
2 Runtime error 171 ms 19132 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 264 ms 20816 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 397 ms 28164 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 559 ms 35344 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 671 ms 40972 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 803 ms 47332 KB Memory limit exceeded
2 Halted 0 ms 0 KB -