fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23. const int N = 100001;
  24. const int MOD = 1e9 + 7;
  25.  
  26. vi adj[N];
  27. bool color[N];
  28. int visited[N];
  29. bool hascolor[N];
  30. bool dfscolor[N];
  31.  
  32. ll ans = 1;
  33.  
  34. bool dfs(int u, bool col, int mx)
  35. {
  36. 	//cerr<<u<<' '<<col<<' '<<visited[u]<<' '<<mx<<'\n';
  37. 	visited[u]++; dfscolor[u] = col;
  38. 	bool ans = true;
  39. 	if(hascolor[u]&&color[u] != col) ans = false;
  40. 	for(int i = 0; i < adj[u].size(); i++)
  41. 	{
  42. 		int v = adj[u][i];
  43. 		if(visited[v] == mx)
  44. 		{
  45. 			if(dfscolor[v] != (col^1))
  46. 			{
  47. 				ans = false;
  48. 			}
  49. 			continue;
  50. 		}
  51. 		bool tmp = dfs(v, (col^1), mx);
  52. 		ans&=tmp;
  53. 	}
  54. 	return ans;
  55. }	
  56.  
  57. int main()
  58. {
  59. 	ios_base::sync_with_stdio(0); cin.tie(0); 
  60. 	int n, m;
  61. 	cin >> n >> m;
  62. 	for(int i = 0; i < m; i++)
  63. 	{
  64. 		int u, v; cin>>u>>v; u--; v--;
  65. 		adj[u].pb(v); adj[v].pb(u);
  66. 	}
  67. 	string s; cin>>s;
  68. 	for(int i = 0; i < n; i++)
  69. 	{
  70. 		hascolor[i] = 1;
  71. 		if(s[i] == 'W') color[i] = 1;
  72. 		else if(s[i] == 'B') color[i] = 0;
  73. 		else hascolor[i] = 0;
  74. 	}
  75. 	for(int i = 0; i < n; i++)
  76. 	{
  77. 		if(visited[i] == 0)
  78. 		{
  79. 			int cnt = 0;
  80. 			if(dfs(i, 0, 1)) cnt++;
  81. 			if(dfs(i, 1, 2)) cnt++;
  82. 			ans = (ans*cnt)%MOD;
  83. 		}
  84. 	}
  85. 	cout << ans << '\n';
  86. }
  87.  
Runtime error #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1QKfmY
language:
C++14 (gcc 8.3)
created:
7 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!