fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h> 
  3. using namespace std;
  4.  
  5. const int maxn = 1e5 + 31; 
  6. const int mod = 1e9 + 7; 
  7. int n, m;
  8. vector<int> depth(maxn), ke[maxn];
  9. vector<int> node_on_depth(maxn, 0); 
  10. vector<int> edge_on_depth(maxn, 0); 
  11. int max_depth; 
  12. int hehepow(long long a, long long b) {
  13.     int res = 1;
  14.     while (b > 0) {
  15.         if (b & 1)
  16.             res = res * a;
  17.         a = a * a;
  18.         b >>= 1;
  19.     }
  20.     return res;
  21. }
  22.  
  23. /*
  24. node_on_depth : so luong node cung do cao  
  25. edge_on_depth : so luong canh cung do cao 
  26. */
  27. // chinh xac  
  28. void init(){
  29.     for(int i = 1;i <= n;i++){
  30.         node_on_depth[depth[i]]++; 
  31.     }
  32.     for(int u = 1;u <= n;u++){
  33.         for(auto v : ke[u]){
  34.             if(depth[u] == depth[v] && u < v) 
  35.                 edge_on_depth[depth[u]]++; 
  36.         }
  37.     }
  38. }
  39. // kiem tra co dap an hay khong  
  40. bool solvable(){
  41.     for(int i = 2;i <= n;i++){
  42.         if(depth[i] == 0) return false;
  43.     }
  44.     for(int i = 1;i <= max_depth;i++){
  45.         if(node_on_depth[i] == 0) return false; 
  46.     }
  47.     for(int i = 1;i <= n;i++){
  48.         for(auto j : ke[i]){
  49.             if(abs(depth[i] - depth[j]) > 1) return false; 
  50.         }
  51.     }
  52.     return true; 
  53. }
  54. // ham solve 
  55. int solve(){
  56.     if(solvable() == false){
  57.     	cout << "hehehe" << endl;  
  58. 		return 0;  
  59. 	} 
  60.  
  61.     int ans = 1;  
  62.  
  63.     // xet cac canh cung tang 
  64. 	for(int i = 1;i <= max_depth;i++){
  65.     	if(node_on_depth[i] > 1){
  66.     		ans = 1ll * ans * hehepow(2, node_on_depth[i] * (node_on_depth[i] - 1) / 2 - edge_on_depth[i]) % mod; 
  67. //			cout << i << " " << ans << endl;  
  68. 		}  
  69. 	}
  70.  
  71. 	// xet cac canh khac tang 
  72. 	for(int u = 2;u <= n;u++){
  73. 		int edge_on = 0;  
  74. 		// v la cha u  
  75. 		for(int v : ke[u]){
  76. 			if(depth[v] == depth[u] - 1) edge_on++;  
  77. 		} 
  78. //		cout << "node " << u << " : ";  
  79. 		int edge_remain = node_on_depth[depth[u] - 1] - edge_on;   
  80. //		cout << edge_remain << " " << edge_on << " ";  
  81. 		if(edge_on){
  82.             ans = 1ll * ans * hehepow(2, edge_remain) % mod; 
  83.         } 
  84.         else{
  85.             ans = 1ll * ans * (hehepow(2, edge_remain) - 1) % mod; 
  86.         }
  87. //		cout << "ans : " << ans << endl; 
  88. 	} 
  89. 	cout << "ahehehe" << endl;  
  90. 	return ans;  
  91. }
  92. void check(){
  93.     for(int i = 1;i <= n;i++){
  94.         cout << "node_on_depth " << i << " : " << node_on_depth[i] << endl; 
  95.     }
  96.     cout << endl;  
  97.     for(int i = 1;i <= n;i++){
  98.         cout << "edge_on_depth " << i << " : " << edge_on_depth[i] << endl; 
  99.     }
  100. }
  101. int main() {
  102.  
  103.     cin >> n >> m;
  104.     for(int i = 1;i <= n;i++) cin >> depth[i]; 
  105.     for(int i = 1;i <= n;i++){
  106.         max_depth = max(max_depth, depth[i]); 
  107.     }
  108.  
  109.     for(int i = 1;i <= m;i++){
  110.         int u, v;
  111.         cin >> u >> v;
  112.         ke[u].push_back(v);
  113.         ke[v].push_back(u); 
  114.     }
  115.     init(); 
  116.  //   check();  
  117.     cout << solve() << endl;  
  118. }
Success #stdin #stdout 0.01s 6668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ahehehe
1
https://ideone.com/BAAuHC
language:
C++14 (gcc 8.3)
created:
7 days 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!