Advertisement
Guest User

Untitled

a guest
Mar 4th, 2018
446
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. # include <sys/time.h>
  4. # include <sys/resource.h>
  5. #endif
  6.  
  7. /*** TEMPLATE CODE STARTS HERE ***/
  8.  
  9. #ifndef M_PI
  10. #define M_PI 3.1415926535897932384626433832795028841971693993751
  11. #endif
  12.  
  13. using namespace std;
  14.  
  15. typedef vector<string> vs;
  16. typedef long long ll;
  17. typedef complex<double> pnt;
  18. typedef vector<int> vi;
  19. typedef vector<ll> vll;
  20. typedef pair<int, int> pii;
  21. typedef pair<ll, ll> pll;
  22.  
  23. #define RA(x) begin(x), end(x)
  24. #define FE(i, x) for (auto i = begin(x); i != end(x); ++i)
  25. #define SZ(x) ((ll) (x).size())
  26.  
  27. template<class T>
  28. void splitstr(const string &s, vector<T> &out)
  29. {
  30.     istringstream in(s);
  31.     out.clear();
  32.     copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
  33. }
  34.  
  35. static void redirect(int argc, const char **argv)
  36. {
  37. #ifndef ONLINE_JUDGE
  38.     struct rlimit rlim;
  39.     getrlimit(RLIMIT_STACK, &rlim);
  40.     rlim.rlim_cur = 256 * 1024 * 1024;
  41.     setrlimit(RLIMIT_STACK, &rlim);
  42. #ifndef __SANITIZE_ADDRESS__
  43.     getrlimit(RLIMIT_DATA, &rlim);
  44.     rlim.rlim_cur = 256 * 1024 * 1024;
  45.     setrlimit(RLIMIT_DATA, &rlim);
  46. #endif
  47. #endif
  48.  
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.     if (argc > 1)
  52.     {
  53.         static filebuf f;
  54.         f.open(argv[1], ios::in);
  55.         cin.rdbuf(&f);
  56.         if (!cin)
  57.         {
  58.             cerr << "Failed to open '" << argv[1] << "'" << endl;
  59.             exit(1);
  60.         }
  61.     }
  62.  
  63.     if (argc > 2)
  64.     {
  65.         static filebuf f;
  66.         f.open(argv[2], ios::out | ios::trunc);
  67.         cout.rdbuf(&f);
  68.         if (!cout)
  69.         {
  70.             cerr << "Failed to open '" << argv[2] << "'" << endl;
  71.         }
  72.     }
  73. }
  74.  
  75. /*** TEMPLATE CODE ENDS HERE */
  76.  
  77. // Undefined sign for negative inputs
  78. template<typename T>
  79. static T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
  80.  
  81. // m must be positive
  82. template<typename T>
  83. static T mod(T a, T m)
  84. {
  85.     a %= m;
  86.     if (a < 0)
  87.         a += m;
  88.     return a;
  89. }
  90.  
  91. // a must be relatively prime to m
  92. template<typename T>
  93. static T inverse(T a, T m)
  94. {
  95.     a = mod(a, m);
  96.     if (a <= 1)
  97.         return a;
  98.     return mod((1 - inverse(m, a) * m) / a, m);
  99. }
  100.  
  101. template<typename T, typename C, T Modulus>
  102. class MR
  103. {
  104. private:
  105.     struct tag_plus {}; // indicates value is in range [0, 2 * Modulus)
  106.     struct tag_minus {}; // indicates value is in range (-Modulus, Modulus)
  107.     struct tag_good {}; // indicates value is in range
  108.  
  109.     T value;
  110.  
  111.     static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0, "compute type is too small");
  112.     static_assert(Modulus < std::numeric_limits<T>::max() / 2, "storage type is too small");
  113.  
  114.     void reduce(tag_plus)
  115.     {
  116.         if (value >= Modulus)
  117.             value -= Modulus;
  118.     }
  119.  
  120.     void reduce(tag_minus)
  121.     {
  122.         if (value < 0)
  123.             value += Modulus;
  124.     }
  125.  
  126.     void reduce(tag_good) {}
  127.  
  128. public:
  129.     typedef T value_type;
  130.     typedef C compute_type;
  131.     static const T modulus = Modulus;
  132.  
  133.     MR() : value(0) {}
  134.     MR(C value) : value(value % Modulus) { reduce(tag_minus()); }
  135.     template<typename tag_t>
  136.     MR(T value, tag_t tag) : value(value) { reduce(tag); }
  137.  
  138.     MR &operator=(C value) { this->value = value % Modulus; reduce(tag_minus()); return *this; }
  139.  
  140.     MR operator +(MR b) const { return MR(value + b.value, tag_plus()); }
  141.     MR operator -(MR b) const { return MR(value - b.value, tag_minus()); }
  142.     MR operator *(MR b) const { return MR(C(value) * C(b.value) % Modulus, tag_good()); }
  143.     MR operator -() const { return MR(-value, tag_minus()); }
  144.  
  145.     MR &operator +=(MR b) { value += b.value; reduce(tag_plus()); return *this; }
  146.     MR &operator -=(MR b) { value -= b.value; reduce(tag_minus()); return *this; }
  147.     MR &operator *=(MR b) { value = C(value) * C(b.value) % Modulus; return *this; }
  148.  
  149.     bool operator==(MR b) const { return value == b.value; }
  150.     bool operator!=(MR b) const { return value != b.value; }
  151.  
  152.     T get() const { return value; }
  153.  
  154.     // These are only valid if the Modulus is prime, or at least if
  155.     // the dividend is relatively prime to the modulus
  156.     MR inverse() const
  157.     {
  158.         assert(value);
  159.         return MR(::inverse(C(value), C(Modulus)), tag_good());
  160.     }
  161.     MR operator /(MR b) const { return *this * b.inverse(); }
  162.     MR &operator /=(MR b) { return *this *= b.inverse(); }
  163. };
  164.  
  165. template<typename T, typename C, T Modulus>
  166. static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr)
  167. {
  168.     return o << mr.get();
  169. }
  170.  
  171. typedef MR<int, ll, 1000000007> mr;
  172.  
  173. int main(int argc, const char **argv)
  174. {
  175.     mr half = mr(1) / mr(2);
  176.  
  177.     redirect(argc, argv);
  178.     int N, M, K;
  179.     cin >> N >> M >> K;
  180.     vector<mr> v(N);
  181.     vi hits(N);
  182.     vector<vi> edges(N);
  183.     vi s(K);
  184.     for (int i = 0; i < N; i++)
  185.     {
  186.         int z;
  187.         cin >> z;
  188.         v[i] = z;
  189.     }
  190.     for (int i = 0; i < K; i++)
  191.     {
  192.         cin >> s[i];
  193.         s[i]--;
  194.         hits[s[i]]++;
  195.     }
  196.     for (int i = 0; i < M; i++)
  197.     {
  198.         int x, y;
  199.         cin >> x >> y;
  200.         x--;
  201.         y--;
  202.         edges[x].push_back(y);
  203.         edges[y].push_back(x);
  204.     }
  205.  
  206.     vector<mr> p2(K + 1);
  207.     p2[0] = 1;
  208.     for (int i = 1; i <= K; i++)
  209.         p2[i] = p2[i - 1] + p2[i - 1];
  210.  
  211.     mr ans = 0;
  212.     vector<mr> scale(N);
  213.     for (int x = 0; x < N; x++)
  214.     {
  215.         if (hits[x] != 0)
  216.             v[x] += v[x] / (p2[hits[x]] - 1);
  217.     }
  218.     for (int i = 0; i < N; i++)
  219.         if (hits[i])
  220.             for (int x : edges[i])
  221.                 if (hits[x] == 0 && v[x] != 0)
  222.                 {
  223.                     cout << "-1\n";
  224.                     return 0;
  225.                 }
  226.  
  227.     for (int a : s)
  228.     {
  229.         ll add = 0;
  230.         for (int x : edges[a])
  231.             add += v[x].get();
  232.         v[a] *= half;
  233.         ans += mr(add);
  234.     }
  235.     cout << ans << '\n';
  236.  
  237.     return 0;
  238. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement