fork download 
  1. #include <algorithm>
  2. #include <array>
  3. #include <assert.h>
  4. #include <bitset>
  5. #include <chrono>
  6. #include <cmath>
  7. #include <complex>
  8. #include <cstring>
  9. #include <functional>
  10. #include <fstream>
  11. #include <iomanip>
  12. #include <iostream>
  13. #include <istream>
  14.  
  15. #include <map>
  16. #include <math.h>
  17. #include <numeric>
  18. #include <ostream>
  19. #include <queue>
  20. #include <set>
  21. #include <stack>
  22. #include <string>
  23. #include <unordered_map>
  24. #include <unordered_set>
  25. #include <vector>
  26.  
  27. namespace asl
  28. {
  29.     typedef long long i64;
  30.  
  31. #include <stdint.h>
  32.  
  33.     template <typename T>
  34.     using vec = std::vector<T>;
  35.  
  36.     class DisjointSet
  37.     {
  38.         bool with_path_compression;
  39.  
  40.     public:
  41.         std::vector<int> ds;
  42.  
  43.         DisjointSet(int n, bool with_path_compression = true) : with_path_compression(with_path_compression)
  44.         {
  45.             ds = std::vector<int>(n, -1);
  46.         }
  47.  
  48.         int root(int a)
  49.         {
  50.             if (ds[a] < 0)
  51.                 return a;
  52.             else
  53.             {
  54.                 if (with_path_compression)
  55.                     return ds[a] = root(ds[a]);
  56.                 else
  57.                     return root(ds[a]);
  58.             }
  59.         }
  60.  
  61.         bool join(int u, int v)
  62.         {
  63.             u = root(u), v = root(v);
  64.  
  65.             if (u == v)
  66.             {
  67.                 on_equal(u);
  68.                 return false;
  69.             }
  70.  
  71.             if (ds[u] < ds[v])
  72.                 std::swap(u, v);
  73.  
  74.             on_join(u, v);
  75.  
  76.             ds[v] += ds[u];
  77.             ds[u] = v;
  78.  
  79.             return true;
  80.         }
  81.  
  82.         virtual void on_join(int u, int v)
  83.         {
  84.         }
  85.  
  86.         virtual void on_equal(int u)
  87.         {
  88.         }
  89.     };
  90. } // namespace asl
  91.  
  92. namespace asl
  93. {
  94.  
  95.     template <typename T>
  96.     std::vector<std::vector<T>> board(int n, int m, T def)
  97.     {
  98.         return std::vector<std::vector<T>>(n, std::vector<T>(m, def));
  99.     }
  100.  
  101.     template <typename T>
  102.     std::vector<std::vector<T>> board(int n = 0, int m = 0)
  103.     {
  104.         return std::vector<std::vector<T>>(n, std::vector<T>(m));
  105.     }
  106.  
  107. } // namespace asl
  108.  
  109. #include <utility>
  110.  
  111. #include <tuple>
  112.  
  113. #include <random>
  114.  
  115. #define endl '\n'
  116.  
  117. using namespace std;
  118. using namespace asl;
  119.  
  120. vec<int> base3(int num)
  121. {
  122.     vec<int> res;
  123.     for (int i = 0; i < 3; ++i)
  124.     {
  125.         res.push_back(num % 3);
  126.         num /= 3;
  127.     }
  128.     return res;
  129. }
  130.  
  131. bool valid(vec<int> &row)
  132. {
  133.     int p = 0;
  134.  
  135.     for (int i = 0; i < 3; ++i)
  136.     {
  137.         if (row[i] > p)
  138.             return false;
  139.         if (row[i] == p)
  140.             ++p;
  141.     }
  142.  
  143.     return true;
  144. }
  145.  
  146. bool test(int mask, int bit)
  147. {
  148.     return mask >> bit & 1;
  149. }
  150.  
  151. vec<int> canonic(vec<int> order)
  152. {
  153.     map<int, int> m;
  154.     int p = 0;
  155.  
  156.     for (int i = 0; i < 3; ++i)
  157.     {
  158.         if (!m.count(order[i]))
  159.             m[order[i]] = p++;
  160.         order[i] = m[order[i]];
  161.     }
  162.     return order;
  163. }
  164.  
  165. struct state
  166. {
  167.     vec<int> order;
  168.     int mask;
  169.  
  170.     bool is_end()
  171.     {
  172.         int t = 0;
  173.         for (int x = 0; x < 3; ++x)
  174.             if (test(mask, x))
  175.             {
  176.                 ++t;
  177.                 for (int y = 0; y < x; ++y)
  178.                     if (order[x] != order[y] && test(mask, y))
  179.                         return false;
  180.             }
  181.         return t > 0;
  182.     }
  183.  
  184.     bool operator==(const state &s) const
  185.     {
  186.         return order == s.order && mask == s.mask;
  187.     }
  188.  
  189. } S[100];
  190.  
  191. int TOTAL;
  192. bool END[100];
  193. bool VALID[100][1 << 5][1 << 3];
  194. int GO[100][1 << 5][1 << 3];
  195.  
  196. void calc(int state_id, int wall, int person)
  197. {
  198.     state s = S[state_id];
  199.     DisjointSet ds(7);
  200.  
  201.     for (int x = 0; x < 3; ++x)
  202.         for (int y = 0; y < 3; ++y)
  203.             if (s.order[x] == s.order[y])
  204.                 ds.join(x, y);
  205.  
  206.     for (int i = 0; i < 3; ++i)
  207.         if (wall >> i & 1)
  208.             ds.join(i, i + 3);
  209.  
  210.     if (wall >> 3 & 1)
  211.         ds.join(3, 4);
  212.  
  213.     if (wall >> 4 & 1)
  214.         ds.join(4, 5);
  215.  
  216.     auto tmp = ds;
  217.     for (int i = 0; i < 3; ++i)
  218.         tmp.join(i + 3, 6);
  219.  
  220.     int r = tmp.root(6);
  221.     for (int i = 0; i < 3; ++i)
  222.         if ((s.mask >> i & 1) && tmp.root(i) != r)
  223.         {
  224.             VALID[state_id][wall][person] = false;
  225.             return;
  226.         }
  227.  
  228.     vec<bool> per(6);
  229.     for (int i = 0; i < 3; ++i)
  230.     {
  231.         if (s.mask >> i & 1)
  232.             per[ds.root(i)] = true;
  233.  
  234.         if (person >> i & 1)
  235.             per[ds.root(i + 3)] = true;
  236.     }
  237.  
  238.     int new_mask = 0;
  239.     vec<int> tmp_ord(3);
  240.  
  241.     for (int i = 0; i < 3; ++i)
  242.     {
  243.         tmp_ord[i] = ds.root(i + 3);
  244.         if (per[ds.root(i + 3)])
  245.             new_mask |= 1 << i;
  246.     }
  247.  
  248.     state ns = {canonic(tmp_ord), new_mask};
  249.     int id = -1;
  250.  
  251.     for (int i = 0; i < TOTAL; ++i)
  252.         if (ns == S[i])
  253.         {
  254.             id = i;
  255.             break;
  256.         }
  257.  
  258.     assert(id >= 0);
  259.     VALID[state_id][wall][person] = true;
  260.     GO[state_id][wall][person] = id;
  261. }
  262.  
  263. void pre()
  264. {
  265.     TOTAL = 0;
  266.     for (int i = 0; i < 27; ++i)
  267.     {
  268.         auto row = base3(i);
  269.  
  270.         if (!valid(row))
  271.             continue;
  272.  
  273.         for (int mask = 0; mask < 8; ++mask)
  274.         {
  275.             bool good = true;
  276.             for (int x = 0; x < 3 && good; ++x)
  277.                 for (int y = 0; y < x && good; ++y)
  278.                     if (row[x] == row[y])
  279.                         good &= test(mask, x) == test(mask, y);
  280.  
  281.             if (!good)
  282.                 continue;
  283.  
  284.             S[TOTAL] = {row, mask};
  285.  
  286.             END[TOTAL] = S[TOTAL].is_end();
  287.             TOTAL++;
  288.         }
  289.     }
  290.  
  291.     int good = 0;
  292.     int bad = 0;
  293.  
  294.     for (int s = 0; s < TOTAL; ++s)
  295.         for (int wall = 0; wall < (1 << 5); ++wall)
  296.             for (int person = 0; person < (1 << 3); ++person)
  297.             {
  298.                 calc(s, wall, person);
  299.  
  300.                 if (VALID[s][wall][person])
  301.                     good++;
  302.                 else
  303.                     bad++;
  304.             }
  305. }
  306.  
  307. void solve()
  308. {
  309.     pre();
  310.  
  311.     int n, m;
  312.     cin >> n >> m;
  313.  
  314.     auto a = board<i64>(3, n, 1e18);
  315.     auto b = board<i64>(2, n);
  316.  
  317.     for (int i = 0; i < 3; ++i)
  318.         for (int j = 1; j < n; ++j)
  319.             cin >> a[i][j];
  320.  
  321.     for (int i = 0; i < 2; ++i)
  322.         for (int j = 0; j < n; ++j)
  323.             cin >> b[i][j];
  324.  
  325.     vec<int> people(n);
  326.     int last = -1;
  327.  
  328.     for (int i = 0; i < m; ++i)
  329.     {
  330.         int x, y;
  331.         cin >> x >> y;
  332.         --x;
  333.         --y;
  334.  
  335.         people[y] |= 1 << x;
  336.         last = max(last, y);
  337.     }
  338.  
  339.     auto cost = [&](int p, int wall) {
  340.         i64 r = 0;
  341.         for (int i = 0; i < 3; ++i)
  342.             if (wall >> i & 1)
  343.                 r += a[i][p];
  344.         if (wall >> 3 & 1)
  345.             r += b[0][p];
  346.         if (wall >> 4 & 1)
  347.             r += b[1][p];
  348.         return r;
  349.     };
  350.  
  351.     const i64 inf = 1e18;
  352.  
  353.     vec<i64> dp(TOTAL, inf);
  354.     vec<i64> memo(1 << 5);
  355.     dp[0] = 0;
  356.  
  357.     i64 res = inf;
  358.  
  359.     for (int i = 0; i < n; ++i)
  360.     {
  361.         vec<i64> ndp(TOTAL, inf);
  362.         int p = people[i];
  363.  
  364.         for (int wall = 0; wall < (1 << 5); ++wall)
  365.             memo[wall] = cost(i, wall);
  366.  
  367.         for (int s = 0; s < TOTAL; ++s)
  368.             for (int wall = 0; wall < (1 << 5); ++wall)
  369.             {
  370.  
  371.                 if (VALID[s][wall][p])
  372.                 {
  373.                     int ns = GO[s][wall][p];
  374.                     ndp[ns] = min(ndp[ns], dp[s] + memo[wall]);
  375.                 }
  376.             }
  377.  
  378.         dp.swap(ndp);
  379.  
  380.         if (i >= last)
  381.             for (int s = 0; s < TOTAL; ++s)
  382.                 if (END[s])
  383.                     res = min(res, dp[s]);
  384.     }
  385.  
  386.     cout << res << endl;
  387. }
  388.  
  389. int main()
  390. {
  391.     ios_base::sync_with_stdio(0);
  392.     cin.tie(0);
  393.  
  394.     int t = 1;
  395.  
  396.     for (int i = 1; i <= t; ++i)
  397.     {
  398.         solve();
  399.     }
  400.  
  401.     return 0;
  402. }
  403.  
Success #stdin #stdout 0s 4880KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000000000000
https://ideone.com/emBhDa
language:
C++14 (clang 8.0)
created:
3 years 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!