fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  5. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  6. #define nl "\n"
  7. #define mp make_pair
  8. #define pb emplace_back
  9. #define sz(s) (int)s.size()
  10. #define all(s) (s).begin(), (s).end()
  11. #define ms(a,x) memset(a, x, sizeof (a))
  12. #define re exit(0)
  13.  
  14. typedef long long ll;
  15. typedef vector<int> vi;
  16.  
  17. const int mod = 666013;
  18. const int maxn = 3005;
  19.  
  20. int n, m, a[maxn], idx[maxn];
  21. vi g[maxn], val, topo;
  22. bool vs[maxn];
  23.  
  24. /// --- Bitset tối ưu dùng uint64_t
  25. struct Bitset64 {
  26.     static const int SZ = 48; // đủ cho 3005 bit
  27.     uint64_t bits[SZ];
  28.  
  29.     Bitset64() { memset(bits, 0, sizeof(bits)); }
  30.  
  31.     void set(int pos) {
  32.         int block = pos / 64;
  33.         int bit = pos % 64;
  34.         bits[block] |= (1ULL << bit);
  35.     }
  36.  
  37.     void reset() {
  38.         memset(bits, 0, sizeof(bits));
  39.     }
  40.  
  41.     Bitset64 operator|(const Bitset64 &other) const {
  42.         Bitset64 res;
  43.         for (int i = 0; i < SZ; i++)
  44.             res.bits[i] = bits[i] | other.bits[i];
  45.         return res;
  46.     }
  47.  
  48.     Bitset64& operator|=(const Bitset64 &other) {
  49.         for (int i = 0; i < SZ; i++)
  50.             bits[i] |= other.bits[i];
  51.         return *this;
  52.     }
  53.  
  54.     Bitset64 operator&(const Bitset64 &other) const {
  55.         Bitset64 res;
  56.         for (int i = 0; i < SZ; i++)
  57.             res.bits[i] = bits[i] & other.bits[i];
  58.         return res;
  59.     }
  60.  
  61.     bool any() const {
  62.         for (int i = 0; i < SZ; i++)
  63.             if (bits[i]) return true;
  64.         return false;
  65.     }
  66.  
  67.     int find_next(int pos) const {
  68.         int block = pos / 64;
  69.         int bit = pos % 64;
  70.  
  71.         if (block >= SZ) return SZ * 64;
  72.  
  73.         uint64_t cur = bits[block] & (~0ULL << bit);
  74.         if (cur != 0) {
  75.             return block * 64 + __builtin_ctzll(cur);
  76.         }
  77.  
  78.         for (int i = block + 1; i < SZ; i++) {
  79.             if (bits[i]) return i * 64 + __builtin_ctzll(bits[i]);
  80.         }
  81.  
  82.         return SZ * 64;
  83.     }
  84. };
  85.  
  86. Bitset64 d[maxn], zero[maxn];
  87.  
  88. void dfs(int u) {
  89.     vs[u] = true;
  90.     for (int v : g[u]) {
  91.         if (!vs[v]) dfs(v);
  92.     }
  93.     topo.pb(u);
  94. }
  95.  
  96. int main() {
  97.     ios_base::sync_with_stdio(false);
  98.     cin.tie(nullptr); cout.tie(nullptr);
  99.  
  100.     cin >> n >> m;
  101.     ff(i, 1, n) {
  102.         cin >> a[i];
  103.         val.pb(a[i]);
  104.     }
  105.  
  106.     // Nén giá trị độ cao
  107.     sort(all(val));
  108.     val.erase(unique(all(val)), val.end());
  109.     ff(i, 1, n) {
  110.         a[i] = (int)(upper_bound(all(val), a[i]) - val.begin()); // 1-based
  111.         idx[a[i]] = i;
  112.     }
  113.  
  114.     // Đọc đồ thị
  115.     ff(i, 1, m) {
  116.         int u, v;
  117.         cin >> u >> v;
  118.         g[u].pb(v);
  119.     }
  120.  
  121.     // Tôpô ngược
  122.     ff(i, 1, n) if (!vs[i]) dfs(i);
  123.  
  124.     // Tạo zero[i] = bitset chứa các bit từ i..n
  125.     for (int i = n; i >= 1; i--) {
  126.         zero[i] = zero[i + 1];
  127.         zero[i].set(i);
  128.     }
  129.  
  130.     // Duyệt topo ngược để xây d[u] = tập đỉnh reachable từ u
  131.     for (int u : topo) {
  132.         d[u].set(a[u]);
  133.         for (int v : g[u]) {
  134.             d[u] |= d[v];
  135.         }
  136.     }
  137.  
  138.     ll ans = 0;
  139.  
  140.     // Tính kết quả theo mô tả đề
  141.     ff(i, 1, n) ff(j, i + 1, n) {
  142.         Bitset64 tmp = d[i] & d[j];
  143.  
  144.         if (!tmp.any()) {
  145.             ans = ans * (n + 1) % mod;
  146.         } else {
  147.             int l = max(a[i], a[j]);
  148.             int pos = tmp.find_next(l);
  149.             int found = (pos > n) ? 0 : idx[pos];
  150.             ans = (ans * (n + 1) + found) % mod;
  151.         }
  152.     }
  153.  
  154.     cout << ans << nl;
  155.     re;
  156. }
  157.  
Success #stdin #stdout 0.01s 5888KB
comments (?)
stdin 
5 7
1 2 3 4 5
1 3
2 3
1 4
2 4
2 5
4 5
3 5
stdout 
24052
https://ideone.com/f7NDQ8
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!