Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("Ofast")
- #include <bits/stdc++.h>
- using namespace std;
- #define sim template < class c
- #define ris return * this
- #define dor > debug & operator <<
- #define eni(x) sim > typename \
- enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
- sim > struct rge {c b, e; };
- sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
- sim > auto dud(c* x) -> decltype(cerr << *x, 0);
- sim > char dud(...);
- struct debug {
- #ifdef LOCAL
- ~debug() { cerr << endl; }
- eni(!=) cerr << boolalpha << i; ris; }
- eni(==) ris << range(begin(i), end(i)); }
- sim, class b dor(pair < b, c > d) {
- ris << "(" << d.first << ", " << d.second << ")";
- }
- sim dor(rge<c> d) {
- *this << "[";
- for (auto it = d.b; it != d.e; ++it)
- *this << ", " + 2 * (it == d.b) << *it;
- ris << "]";
- }
- #else
- sim dor(const c&) { ris; }
- #endif
- };
- #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- typedef long long ll;
- const int mod = 1e9 + 7;
- void add_self(int & a, int b) { a += b; if(a >= mod) a -= mod; }
- int mul(int a, int b) { return (ll) a * b % mod; }
- int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; }
- int my_pow(int a, int b) {
- int r = 1;
- while(b) {
- if(b % 2) r = mul(r, a);
- a = mul(a, a);
- b /= 2;
- }
- return r;
- }
- int my_inv(int a) { return my_pow(a, mod - 2); }
- const int INV_TWO = my_inv(2);
- const int nax = 1e5 + 5;
- vector<int> edges[nax];
- const int MAGIC = 300;
- vector<int> edges_heavy[nax];
- int main() {
- int n, m, k;
- scanf("%d%d%d", &n, &m, &k);
- vector<int> value(n);
- for(int & x : value) scanf("%d", &x);
- vector<int> order(k);
- for(int & x : order) {
- scanf("%d", &x);
- --x;
- }
- for(int rep = 0; rep < m; ++rep) {
- int a, b;
- scanf("%d%d", &a, &b);
- --a;
- --b;
- edges[a].push_back(b);
- edges[b].push_back(a);
- }
- vector<bool> is_heavy(n);
- for(int a = 0; a < n; ++a)
- is_heavy[a] = (int) edges[a].size() >= MAGIC;
- for(int a = 0; a < n; ++a)
- for(int b : edges[a])
- if(is_heavy[b])
- edges_heavy[a].push_back(b);
- vector<int> occurrences(n);
- for(int x : order) ++occurrences[x];
- vector<int> current_value(n);
- for(int a = 0; a < n; ++a) {
- if(occurrences[a] == 0) {
- if(value[a] == 0) current_value[a] = 0;
- else current_value[a] = -1;
- }
- else {
- int q = my_pow(INV_TWO, occurrences[a]);
- current_value[a] = mul(value[a], my_inv(sub(1, q)));
- }
- }
- vector<bool> allowed(n, true);
- for(int a = 0; a < n; ++a) {
- for(int b : edges[a])
- if(current_value[b] == -1)
- allowed[a] = false;
- }
- for(int x : order) if(!allowed[x]) {
- puts("-1");
- return 0;
- }
- int answer = 0;
- vector<int> hack(n);
- for(int a = 0; a < n; ++a)
- for(int b : edges[a]) if(!is_heavy[b])
- add_self(hack[a], current_value[b]);
- for(int x : order) {
- add_self(answer, hack[x]);
- for(int y : edges_heavy[x]) add_self(answer, current_value[y]);
- int new_value = mul(INV_TWO, current_value[x]);
- int diff = sub(new_value, current_value[x]);
- current_value[x] = new_value;
- if(!is_heavy[x]) for(int y : edges[x]) add_self(hack[y], diff);
- }
- printf("%d\n", answer);
- }
Add Comment
Please, Sign In to add comment