fork download
copy 
  1. // pSaurabh
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define read(a, n) for(int i = 0; i < n; ++i) cin >> a[i];
  7. #define print(a, n) for(int i = 0; i < n; ++i) if(i == n - 1){ cout << a[i] << "\n"; } else { cout << a[i] << ' '; }
  8.  
  9. typedef long long ll;
  10. typedef long double ld;
  11.  
  12. const ll mod = 1e9 + 7;
  13. const int maxSize = 5e5 + 5;
  14.  
  15. void fast(){
  16. 	ios_base::sync_with_stdio(0);
  17. 	cin.tie(0);
  18. 	cout.tie(0);
  19. }
  20.  
  21. vector <vector <int>> adjP(maxSize);
  22. vector <vector <int>> adjH(maxSize);
  23. vector <vector <int>> adj (maxSize);
  24. vector <char> assigned(maxSize, 'N');
  25. vector <bool> vis(maxSize, 0);
  26.  
  27. bool dfs(int root, char type){
  28.  
  29. 	if(assigned[root] == 'N'){
  30. 		assigned[root] = type;
  31. 	}
  32. 	else{
  33. 		if(type != assigned[root]){
  34. 			return 0;
  35. 		}
  36. 	}
  37.  
  38. 	if(vis[root]) return 1;
  39.  
  40. 	vis[root] = 1;
  41.  
  42. 	if(type == 'H'){
  43. 		bool isConsistent = 1;
  44.  
  45. 		for(auto it : adjP[root]){
  46. 			isConsistent &= dfs(it, 'P');
  47. 		}
  48. 		for(auto it : adjH[root]){
  49. 			isConsistent &= dfs(it, 'H');
  50. 		}
  51. 		return isConsistent;
  52. 	}
  53. 	else{
  54. 		bool isConsistent = 1;
  55.  
  56. 		for(auto it : adjP[root]){
  57. 			isConsistent &= dfs(it, 'H');
  58. 		}
  59. 		for(auto it : adjH[root]){
  60. 			isConsistent &= dfs(it, 'P');
  61. 		}
  62. 		return isConsistent;
  63. 	}
  64.  
  65. 	return 1;
  66. }
  67.  
  68. int getParasiteCnt(int root){
  69.  
  70. 	vis[root] = 1;
  71. 	int ans = (assigned[root] == 'P');
  72. 	for(auto it : adj[root]){
  73. 		if(!vis[it]){
  74. 			ans += getParasiteCnt(it);
  75. 		}
  76. 	}
  77. 	return ans;
  78. }
  79.  
  80. void clearOnlyVis(int root){
  81. 	vis[root] = 0;
  82.  
  83. 	for(auto it : adj[root]){
  84. 		if(vis[it]){
  85. 			clearOnlyVis(it);
  86. 		}
  87. 	}
  88. }
  89.  
  90. void clearVisAssigned(int root){
  91. 	vis[root] = 0;
  92. 	assigned[root] = 'N';
  93.  
  94. 	for(auto it : adj[root]){
  95. 		if(vis[it]){
  96. 			clearVisAssigned(it);
  97. 		}
  98. 	}
  99. }
  100.  
  101. int main(){
  102. 	fast();
  103.  
  104. 	int t;
  105. 	cin >> t;
  106.  
  107. 	while(t--){
  108.  
  109. 		int n, m;
  110. 		cin >> n >> m;
  111.  
  112. 		for(int i = 0; i <= n; ++i){
  113. 			adjP[i].clear();
  114. 			adjH[i].clear();
  115. 			adj[i].clear();
  116. 			assigned[i] = 'N';
  117. 			vis[i] = 0;
  118. 		}
  119.  
  120. 		for(int i = 0; i < m; ++i){
  121. 			int type, u, v;
  122. 			cin >> type >> u >> v;
  123.  
  124. 			if(type == 1){
  125. 				adjP[u].push_back(v);
  126. 				adjP[v].push_back(u);
  127. 			}
  128. 			else{
  129. 				adjH[u].push_back(v);
  130. 				adjH[v].push_back(u);
  131. 			}
  132.  
  133. 			adj[u].push_back(v);
  134. 			adj[v].push_back(u);
  135. 		}
  136.  
  137. 		int ans = 0;
  138. 		bool ok = 1;
  139. 		bool cons = 1;
  140.  
  141. 		for(int i = 1; i <= n; ++i){
  142. 			if(!vis[i]){
  143. 				int cnt = -1;
  144.  
  145. 				ok = dfs(i, 'H');
  146. 				clearOnlyVis(i);
  147. 				if(ok){
  148. 					cnt = getParasiteCnt(i);
  149. 				}
  150.  
  151. 				clearVisAssigned(i);
  152.  
  153. 				ok = dfs(i, 'P');
  154. 				clearOnlyVis(i);
  155. 				if(ok){
  156. 					cnt = max(cnt, getParasiteCnt(i));
  157. 				}
  158.  
  159. 				if(cnt == -1){
  160. 					cons = 0;
  161. 					break;
  162. 				}
  163.  
  164. 				ans += cnt;
  165. 			}
  166. 		}
  167.  
  168. 		if(!cons){
  169. 			cout << -1 << "\n";
  170. 		}
  171. 		else cout << ans << "\n";
  172. 	}
  173.  
  174. 	return 0;	
  175. }
  176.  
Runtime error #stdin #stdout 4.27s 2095928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KbQhn5
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!