Guest User

Untitled

a guest
Mar 3rd, 2018
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #pragma GCC optimize ("Ofast")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define sim template < class c
  5. #define ris return * this
  6. #define dor > debug & operator <<
  7. #define eni(x) sim > typename \
  8.   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  9. sim > struct rge {c b, e; };
  10. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  11. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  12. sim > char dud(...);
  13. struct debug {
  14. #ifdef LOCAL
  15. ~debug() { cerr << endl; }
  16. eni(!=) cerr << boolalpha << i; ris; }
  17. eni(==) ris << range(begin(i), end(i)); }
  18. sim, class b dor(pair < b, c > d) {
  19.   ris << "(" << d.first << ", " << d.second << ")";
  20. }
  21. sim dor(rge<c> d) {
  22.   *this << "[";
  23.   for (auto it = d.b; it != d.e; ++it)
  24.     *this << ", " + 2 * (it == d.b) << *it;
  25.   ris << "]";
  26. }
  27. #else
  28. sim dor(const c&) { ris; }
  29. #endif
  30. };
  31. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  32.  
  33. typedef long long ll;
  34.  
  35. const int mod = 1e9 + 7;
  36.  
  37. void add_self(int & a, int b) { a += b; if(a >= mod) a -= mod; }
  38. int mul(int a, int b) { return (ll) a * b % mod; }
  39. int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; }
  40. int my_pow(int a, int b) {
  41.     int r = 1;
  42.     while(b) {
  43.         if(b % 2) r = mul(r, a);
  44.         a = mul(a, a);
  45.         b /= 2;
  46.     }
  47.     return r;
  48. }
  49. int my_inv(int a) { return my_pow(a, mod - 2); }
  50. const int INV_TWO = my_inv(2);
  51.  
  52. const int nax = 1e5 + 5;
  53. vector<int> edges[nax];
  54. const int MAGIC = 300;
  55. vector<int> edges_heavy[nax];
  56.  
  57. int main() {
  58.     int n, m, k;
  59.     scanf("%d%d%d", &n, &m, &k);
  60.     vector<int> value(n);
  61.     for(int & x : value) scanf("%d", &x);
  62.     vector<int> order(k);
  63.     for(int & x : order) {
  64.         scanf("%d", &x);
  65.         --x;
  66.     }
  67.     for(int rep = 0; rep < m; ++rep) {
  68.         int a, b;
  69.         scanf("%d%d", &a, &b);
  70.         --a;
  71.         --b;
  72.         edges[a].push_back(b);
  73.         edges[b].push_back(a);
  74.     }
  75.     vector<bool> is_heavy(n);
  76.     for(int a = 0; a < n; ++a)
  77.         is_heavy[a] = (int) edges[a].size() >= MAGIC;
  78.     for(int a = 0; a < n; ++a)
  79.         for(int b : edges[a])
  80.             if(is_heavy[b])
  81.                 edges_heavy[a].push_back(b);
  82.     vector<int> occurrences(n);
  83.     for(int x : order) ++occurrences[x];
  84.     vector<int> current_value(n);
  85.     for(int a = 0; a < n; ++a) {
  86.         if(occurrences[a] == 0) {
  87.             if(value[a] == 0) current_value[a] = 0;
  88.             else current_value[a] = -1;
  89.         }
  90.         else {
  91.             int q = my_pow(INV_TWO, occurrences[a]);
  92.             current_value[a] = mul(value[a], my_inv(sub(1, q)));
  93.         }
  94.     }
  95.     vector<bool> allowed(n, true);
  96.     for(int a = 0; a < n; ++a) {
  97.         for(int b : edges[a])
  98.             if(current_value[b] == -1)
  99.                 allowed[a] = false;
  100.     }
  101.     for(int x : order) if(!allowed[x]) {
  102.         puts("-1");
  103.         return 0;
  104.     }
  105.     int answer = 0;
  106.     vector<int> hack(n);
  107.     for(int a = 0; a < n; ++a)
  108.         for(int b : edges[a]) if(!is_heavy[b])
  109.             add_self(hack[a], current_value[b]);
  110.     for(int x : order) {
  111.         add_self(answer, hack[x]);
  112.         for(int y : edges_heavy[x]) add_self(answer, current_value[y]);
  113.         int new_value = mul(INV_TWO, current_value[x]);
  114.         int diff = sub(new_value, current_value[x]);
  115.         current_value[x] = new_value;
  116.         if(!is_heavy[x]) for(int y : edges[x]) add_self(hack[y], diff);
  117.     }
  118.     printf("%d\n", answer);
  119. }
Add Comment
Please, Sign In to add comment