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