oj.uz

Submission #669290

# Submission time Handle Problem Language Result Execution time Memory
669290 2022-12-06T08:07:48 Z manizare Pipes (CEOI15_pipes) C++17
20 / 100
 1100 ms 14568 KB 
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end() 
#define pb push_back
using namespace std ;
const int maxn = 1e5+100 , maxq =5002 , inf = 2e17 + 100 , mod = 1e9 + 7 ;
vector <int >G[maxn] ;
int par[maxn] , par2[maxn] , p[maxn] , dp[maxn] , mark[maxn] , dis[maxn];
int find(int v){
	if(par[v] == v)return v; 
	return par[v] = find(par[v]);
}
int find2(int v){
	if(par2[v] == v)return v; 
	return par2[v] = find2(par2[v]) ;
}

void dfs(int v){
	mark[v] = 1; 
	for(int i = 0 ; i < G[v].size() ; i++){
		int u = G[v][i] ;
		if(mark[u] == 1){
			if(dis[u] < (dis[v] - 1)){
				dp[v] ++ ;
				dp[u]--;
			}
			continue ;
		}
		dis[u] = dis[v] + 1; 
		p[u] = v; 
		dfs(u);
		dp[v] += dp[u] ;
	}
}

signed main(){	
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	int n , m ;
	cin >> n >> m ;
	for(int i= 1 ; i <= n ; i++){
		par[i] = i ;
		par2[i] = i ; 
	}
	for(int i =1 ; i <= m ; i++){
		int v  , u ;
		cin >> v >> u ;
		int v1 = find(v) , u1 = find(u);
		if(v1 != u1){
			G[v].pb(u) ;
			G[u].pb(v);
			par[v1] = u1 ;
		}else if(find2(v) != find2(u)){
			par2[find2(v)] = find2(u);
			G[v].pb(u) ;
			G[u].pb(v);
		}
	}
	for(int i = 1; i <= n ; i++){
		if(mark[i] == 0)dfs(i); 
	}
	for(int i = 1; i <= n ; i++){
		if(dp[i] == 0 && p[i] != 0){
			cout << i << " " << p[i] << "\n";
		}
	}
}

Compilation message

pipes.cpp:5:52: warning: overflow in conversion from 'double' to 'int' changes value from '2.000000000000001e+17' to '2147483647' [-Woverflow]
    5 | const int maxn = 1e5+100 , maxq =5002 , inf = 2e17 + 100 , mod = 1e9 + 7 ;
      |                                               ~~~~~^~~~~
pipes.cpp: In function 'void dfs(int)':
pipes.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3156 KB Output is correct
2 Incorrect 5 ms 2900 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2976 KB Output is correct
2 Incorrect 80 ms 2892 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 5228 KB Output is correct
2 Correct 194 ms 5052 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 10520 KB Output is correct
2 Incorrect 284 ms 7568 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 11672 KB Output is correct
2 Incorrect 504 ms 11704 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 13756 KB Output is correct
2 Incorrect 740 ms 14568 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 13752 KB Output is correct
2 Incorrect 845 ms 12540 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 13220 KB Output is correct
2 Correct 1024 ms 13924 KB Output is correct