Advertisement
Guest User

Untitled

a guest
Mar 3rd, 2018
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #pragma warning(disable:4786)
  2. #pragma warning(disable:4996)
  3. #include<list>
  4. #include<bitset>
  5. #include<iostream>
  6. #include<cstdio>
  7. #include<algorithm>
  8. #include<vector>
  9. #include<set>
  10. #include<map>
  11. #include<functional>
  12. #include<string>
  13. #include<cstring>
  14. #include<cstdlib>
  15. #include<queue>
  16. #include<utility>
  17. #include<fstream>
  18. #include<sstream>
  19. #include<cmath>
  20. #include<stack>
  21. #include<assert.h>
  22. using namespace std;
  23.  
  24. #define MEM(a, b) memset(a, (b), sizeof(a))
  25. #define CLR(a) memset(a, 0, sizeof(a))
  26. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  27. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  28. #define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
  29. #define S(X) ( (X) * (X) )
  30. #define SZ(V) (int )V.size()
  31. #define FORN(i, n) for(i = 0; i < n; i++)
  32. #define FORAB(i, a, b) for(i = a; i <= b; i++)
  33. #define ALL(V) V.begin(), V.end()
  34. #define IN(A, B, C) ((B) <= (A) && (A) <= (C))
  35.  
  36. typedef pair<int,int> PII;
  37. typedef pair<double, double> PDD;
  38. typedef vector<int> VI;
  39. typedef vector<PII > VP;
  40.  
  41. #define AIN(A, B, C) assert(IN(A, B, C))
  42.  
  43. //typedef int LL;
  44. typedef long long int LL;
  45. //typedef __int64 LL;
  46.  
  47. const LL mod = 1000000007;
  48. LL bigmod(LL a, LL b) {
  49. if (b == 0) return 1;
  50. LL x = bigmod(a, b / 2);
  51. x = (x * x) % mod;
  52. if (b & 1) x = (x * a) % mod;
  53. return x;
  54. }
  55.  
  56. int n, m, k;
  57. LL v[100005];
  58. int s[100005];
  59.  
  60. VI V[100005];
  61.  
  62. int mark[100005], vis[100005];
  63.  
  64. void flood() {
  65. for (int i = 1; i <= n; i++) {
  66. if (!mark[i]) continue;
  67. for (int v : V[i]) {
  68. vis[v] = 1;
  69. }
  70. }
  71. }
  72.  
  73. VI G[100005];
  74. int cnt[100005];
  75. LL p2[100005];
  76.  
  77. int main()
  78. {
  79. scanf("%d %d %d", &n, &m, &k);
  80. for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);
  81. for (int i = 1; i <= k; i++) scanf("%d", &s[i]);
  82. for (int i = 1; i <= m; i++) {
  83. int u, v;
  84. scanf("%d %d", &u, &v);
  85. V[u].push_back(v);
  86. V[v].push_back(u);
  87. }
  88.  
  89. for (int i = 1; i <= k; i++) {
  90. mark[s[i]] = 1;
  91. }
  92. flood();
  93. for (int i = 1; i <= n; i++) {
  94. if (vis[i] && v[i] && !mark[i]) {
  95. printf("-1\n");
  96. return 0;
  97. }
  98. }
  99.  
  100. for (int i = 1; i <= k; i++) {
  101. int u = s[i];
  102. for (int v : V[u]) {
  103. G[v].push_back(cnt[v]);
  104. }
  105. cnt[u]++;
  106. }
  107.  
  108. p2[0] = 1;
  109. for (int i = 1; i <= MAX(n, k); i++) {
  110. p2[i] = (p2[i - 1] * 2) % mod;
  111. }
  112. LL ans = 0;
  113. for (int i = 1; i <= n; i++) {
  114. LL now = 0;
  115. for (int x : G[i]) {
  116. now = (now + p2[cnt[i] - x]);
  117. }
  118. now %= mod;
  119. now = (now * v[i]) % mod;
  120. now = (now * bigmod(p2[cnt[i]] + mod - 1, mod - 2)) % mod;
  121. ans += now;
  122. }
  123. ans %= mod;
  124. printf("%lld\n", ans);
  125. return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement