Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #ifndef ONLINE_JUDGE
- # include <sys/time.h>
- # include <sys/resource.h>
- #endif
- /*** TEMPLATE CODE STARTS HERE ***/
- #ifndef M_PI
- #define M_PI 3.1415926535897932384626433832795028841971693993751
- #endif
- using namespace std;
- typedef vector<string> vs;
- typedef long long ll;
- typedef complex<double> pnt;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- #define RA(x) begin(x), end(x)
- #define FE(i, x) for (auto i = begin(x); i != end(x); ++i)
- #define SZ(x) ((ll) (x).size())
- template<class T>
- void splitstr(const string &s, vector<T> &out)
- {
- istringstream in(s);
- out.clear();
- copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
- }
- static void redirect(int argc, const char **argv)
- {
- #ifndef ONLINE_JUDGE
- struct rlimit rlim;
- getrlimit(RLIMIT_STACK, &rlim);
- rlim.rlim_cur = 256 * 1024 * 1024;
- setrlimit(RLIMIT_STACK, &rlim);
- #ifndef __SANITIZE_ADDRESS__
- getrlimit(RLIMIT_DATA, &rlim);
- rlim.rlim_cur = 256 * 1024 * 1024;
- setrlimit(RLIMIT_DATA, &rlim);
- #endif
- #endif
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- if (argc > 1)
- {
- static filebuf f;
- f.open(argv[1], ios::in);
- cin.rdbuf(&f);
- if (!cin)
- {
- cerr << "Failed to open '" << argv[1] << "'" << endl;
- exit(1);
- }
- }
- if (argc > 2)
- {
- static filebuf f;
- f.open(argv[2], ios::out | ios::trunc);
- cout.rdbuf(&f);
- if (!cout)
- {
- cerr << "Failed to open '" << argv[2] << "'" << endl;
- }
- }
- }
- /*** TEMPLATE CODE ENDS HERE */
- // Undefined sign for negative inputs
- template<typename T>
- static T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
- // m must be positive
- template<typename T>
- static T mod(T a, T m)
- {
- a %= m;
- if (a < 0)
- a += m;
- return a;
- }
- // a must be relatively prime to m
- template<typename T>
- static T inverse(T a, T m)
- {
- a = mod(a, m);
- if (a <= 1)
- return a;
- return mod((1 - inverse(m, a) * m) / a, m);
- }
- template<typename T, typename C, T Modulus>
- class MR
- {
- private:
- struct tag_plus {}; // indicates value is in range [0, 2 * Modulus)
- struct tag_minus {}; // indicates value is in range (-Modulus, Modulus)
- struct tag_good {}; // indicates value is in range
- T value;
- static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0, "compute type is too small");
- static_assert(Modulus < std::numeric_limits<T>::max() / 2, "storage type is too small");
- void reduce(tag_plus)
- {
- if (value >= Modulus)
- value -= Modulus;
- }
- void reduce(tag_minus)
- {
- if (value < 0)
- value += Modulus;
- }
- void reduce(tag_good) {}
- public:
- typedef T value_type;
- typedef C compute_type;
- static const T modulus = Modulus;
- MR() : value(0) {}
- MR(C value) : value(value % Modulus) { reduce(tag_minus()); }
- template<typename tag_t>
- MR(T value, tag_t tag) : value(value) { reduce(tag); }
- MR &operator=(C value) { this->value = value % Modulus; reduce(tag_minus()); return *this; }
- MR operator +(MR b) const { return MR(value + b.value, tag_plus()); }
- MR operator -(MR b) const { return MR(value - b.value, tag_minus()); }
- MR operator *(MR b) const { return MR(C(value) * C(b.value) % Modulus, tag_good()); }
- MR operator -() const { return MR(-value, tag_minus()); }
- MR &operator +=(MR b) { value += b.value; reduce(tag_plus()); return *this; }
- MR &operator -=(MR b) { value -= b.value; reduce(tag_minus()); return *this; }
- MR &operator *=(MR b) { value = C(value) * C(b.value) % Modulus; return *this; }
- bool operator==(MR b) const { return value == b.value; }
- bool operator!=(MR b) const { return value != b.value; }
- T get() const { return value; }
- // These are only valid if the Modulus is prime, or at least if
- // the dividend is relatively prime to the modulus
- MR inverse() const
- {
- assert(value);
- return MR(::inverse(C(value), C(Modulus)), tag_good());
- }
- MR operator /(MR b) const { return *this * b.inverse(); }
- MR &operator /=(MR b) { return *this *= b.inverse(); }
- };
- template<typename T, typename C, T Modulus>
- static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr)
- {
- return o << mr.get();
- }
- typedef MR<int, ll, 1000000007> mr;
- int main(int argc, const char **argv)
- {
- mr half = mr(1) / mr(2);
- redirect(argc, argv);
- int N, M, K;
- cin >> N >> M >> K;
- vector<mr> v(N);
- vi hits(N);
- vector<vi> edges(N);
- vi s(K);
- for (int i = 0; i < N; i++)
- {
- int z;
- cin >> z;
- v[i] = z;
- }
- for (int i = 0; i < K; i++)
- {
- cin >> s[i];
- s[i]--;
- hits[s[i]]++;
- }
- for (int i = 0; i < M; i++)
- {
- int x, y;
- cin >> x >> y;
- x--;
- y--;
- edges[x].push_back(y);
- edges[y].push_back(x);
- }
- vector<mr> p2(K + 1);
- p2[0] = 1;
- for (int i = 1; i <= K; i++)
- p2[i] = p2[i - 1] + p2[i - 1];
- mr ans = 0;
- vector<mr> scale(N);
- for (int x = 0; x < N; x++)
- {
- if (hits[x] != 0)
- v[x] += v[x] / (p2[hits[x]] - 1);
- }
- for (int i = 0; i < N; i++)
- if (hits[i])
- for (int x : edges[i])
- if (hits[x] == 0 && v[x] != 0)
- {
- cout << "-1\n";
- return 0;
- }
- for (int a : s)
- {
- ll add = 0;
- for (int x : edges[a])
- add += v[x].get();
- v[a] *= half;
- ans += mr(add);
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement