fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define SPED                                                                                                           \
  4.     ios_base::sync_with_stdio(false);                                                                                  \
  5.     cin.tie(0);                                                                                                        \
  6.     cout.tie(0);
  7.  
  8. #define endl "\n"
  9. #define fi first
  10. #define se second
  11. #define lint long long
  12. #define fami signed
  13. #define lore main
  14. #define freefire freopen
  15. #define rect tuple<lint, lint, lint, lint>
  16. #define Data tuple<lint, bool, int>
  17.  
  18. const lint INF = 0x1f1f1f1f1f1f1f1f;
  19. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  20.  
  21. using namespace std;
  22.  
  23. struct Button
  24. {
  25.     lint X, Y, CX, CY, ID; // tọa độ và tạo độ đc nén,
  26.     int idH, idC;          // idhàng là id của cột Y trên hàng CX
  27.                            // idcột là id của hàng X trên cột CY
  28. };
  29.  
  30. int t, p, q, dp[2005][2005], hpref[2005][2005], cpref[2005][2005];
  31. lint m, n, dist[2][100005];
  32. Button a[100005];
  33. rect b[100005];
  34. vector<pair<lint, int>> adjh[200005],
  35.     adjc[200005]; // adjhang, adjcot, nghia la cac tk chung hang thi chung 1 vector, chug cot thi chung 1 vector
  36.  
  37. void reset()
  38. {
  39.     for (int i = 1; i <= p + 2; i++)
  40.     {
  41.         adjh[i].clear();
  42.         adjc[i].clear();
  43.     }
  44. }
  45.  
  46. void reset1()
  47. {
  48.     for (int i = 1; i <= p + 2; i++)
  49.     {
  50.         adjh[i].clear();
  51.         adjc[i].clear();
  52.     }
  53.     for (int i = 0; i <= m + 2; i++)
  54.         for (int j = 0; j <= n + 2; j++)
  55.             dp[i][j] = 0;
  56. }
  57.  
  58. /*
  59.     quy ước : 0 là UD
  60.          1 là LR
  61. */
  62.  
  63. inline bool bR(lint X, lint yA, lint yB)
  64. {
  65.     lint L = min(yA, yB), R = max(yA, yB);
  66.     for (int j = 1; j <= q; ++j)
  67.     {
  68.         auto [x1, y1, x2, y2] = b[j];
  69.         if (x1 <= X and X <= x2)
  70.         {
  71.             if (!(R < y1 or y2 < L))
  72.                 return true;
  73.         }
  74.     }
  75.     return false;
  76. }
  77.  
  78. inline bool bC(lint Y, lint xA, lint xB)
  79. {
  80.     lint L = min(xA, xB), R = max(xA, xB);
  81.     for (int j = 1; j <= q; ++j)
  82.     {
  83.         auto [x1, y1, x2, y2] = b[j];
  84.         if (y1 <= Y and Y <= y2)
  85.         {
  86.             if (!(R < x1 or x2 < L))
  87.                 return true;
  88.         }
  89.     }
  90.     return false;
  91. }
  92.  
  93. void dijkstra()
  94. {
  95.     fill(dist[0], dist[0] + p + 2, INF);
  96.     fill(dist[1], dist[1] + p + 2, INF);
  97.  
  98.     dist[0][0] = 0;
  99.  
  100.     priority_queue<Data, vector<Data>, greater<Data>> pq;
  101.  
  102.     pq.emplace(0, 0, 0);
  103.  
  104.     while (!pq.empty())
  105.     {
  106.         auto [du, mode, u] = pq.top();
  107.         pq.pop();
  108.         if (du > dist[mode][u])
  109.             continue;
  110.  
  111.         auto [idx, idy, cidx, cidy, id, idh, idc] = a[u];
  112.  
  113.         if (1 <= u and u <= p)
  114.         {
  115.             if (dist[!mode][u] > dist[mode][u] + 1)
  116.             {
  117.                 dist[!mode][u] = dist[mode][u] + 1;
  118.                 pq.emplace(dist[!mode][u], !mode, u);
  119.             }
  120.         }
  121.  
  122.         if (mode == 1)
  123.         {
  124.             if (idh > 0)
  125.             {
  126.                 auto [w_adj, id_adj] = adjh[cidx][idh - 1];
  127.                 if (!bR(idx, idy, w_adj) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idy))
  128.                 {
  129.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idy);
  130.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  131.                 }
  132.             }
  133.             if (idh < adjh[cidx].size() - 1)
  134.             {
  135.                 auto [w_adj, id_adj] = adjh[cidx][idh + 1];
  136.                 if (!bR(idx, idy, w_adj) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idy))
  137.                 {
  138.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idy);
  139.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  140.                 }
  141.             }
  142.         }
  143.         else
  144.         {
  145.             if (idc > 0)
  146.             {
  147.                 auto [w_adj, id_adj] = adjc[cidy][idc - 1];
  148.                 if (!bC(idy, idx, w_adj) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idx))
  149.                 {
  150.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idx);
  151.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  152.                 }
  153.             }
  154.             if (idc < adjc[cidy].size() - 1)
  155.             {
  156.                 auto [w_adj, id_adj] = adjc[cidy][idc + 1];
  157.                 if (!bC(idy, idx, w_adj) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idx))
  158.                 {
  159.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idx);
  160.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  161.                 }
  162.             }
  163.         }
  164.     }
  165. }
  166.  
  167. void dijkstra1()
  168. {
  169.     fill(dist[0], dist[0] + p + 2, INF);
  170.     fill(dist[1], dist[1] + p + 2, INF);
  171.  
  172.     dist[0][0] = 0;
  173.  
  174.     priority_queue<Data, vector<Data>, greater<Data>> pq;
  175.  
  176.     pq.emplace(0, 0, 0);
  177.  
  178.     while (!pq.empty())
  179.     {
  180.         auto [du, mode, u] = pq.top();
  181.         pq.pop();
  182.         if (du > dist[mode][u])
  183.             continue;
  184.  
  185.         auto [idx, idy, cidx, cidy, id, idh, idc] = a[u];
  186.  
  187.         if (1 <= u and u <= p)
  188.         {
  189.             if (dist[!mode][u] > dist[mode][u] + 1)
  190.             {
  191.                 dist[!mode][u] = dist[mode][u] + 1;
  192.                 pq.emplace(dist[!mode][u], !mode, u);
  193.             }
  194.         }
  195.  
  196.         if (mode == 1)
  197.         {
  198.             if (idh > 0)
  199.             {
  200.                 auto [w_adj, id_adj] = adjh[cidx][idh - 1];
  201.                 lint XX = a[id_adj].X;
  202.                 lint YY = a[id_adj].Y;
  203.                 if (!(hpref[XX][idy] - hpref[XX][YY - 1]) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idy))
  204.                 {
  205.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idy);
  206.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  207.                 }
  208.             }
  209.             if (idh < adjh[cidx].size() - 1)
  210.             {
  211.                 auto [w_adj, id_adj] = adjh[cidx][idh + 1];
  212.                 lint XX = a[id_adj].X;
  213.                 lint YY = a[id_adj].Y;
  214.                 if (!(hpref[XX][YY] - hpref[XX][idy - 1]) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idy))
  215.                 {
  216.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idy);
  217.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  218.                 }
  219.             }
  220.         }
  221.         else
  222.         {
  223.             if (idc > 0)
  224.             {
  225.                 auto [w_adj, id_adj] = adjc[cidy][idc - 1];
  226.                 lint XX = a[id_adj].X;
  227.                 lint YY = a[id_adj].Y;
  228.                 if (!(cpref[idx][YY] - cpref[XX - 1][YY]) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idx))
  229.                 {
  230.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idx);
  231.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  232.                 }
  233.             }
  234.             if (idc < adjc[cidy].size() - 1)
  235.             {
  236.                 auto [w_adj, id_adj] = adjc[cidy][idc + 1];
  237.                 lint XX = a[id_adj].X;
  238.                 lint YY = a[id_adj].Y;
  239.                 if (!(cpref[XX][YY] - cpref[idx - 1][YY]) and dist[mode][id_adj] > dist[mode][u] + abs(w_adj - idx))
  240.                 {
  241.                     dist[mode][id_adj] = dist[mode][u] + abs(w_adj - idx);
  242.                     pq.emplace(dist[mode][id_adj], mode, id_adj);
  243.                 }
  244.             }
  245.         }
  246.     }
  247. }
  248.  
  249. void compress()
  250.  
  251. {
  252.     vector<pair<lint, int>> vx, vy;
  253.     for (int i = 0; i <= p + 1; i++)
  254.         vx.emplace_back(a[i].X, i);
  255.     for (int i = 0; i <= p + 1; i++)
  256.         vy.emplace_back(a[i].Y, i);
  257.     sort(vx.begin(), vx.end());
  258.     sort(vy.begin(), vy.end());
  259.     int cx = 0, cy = 0;
  260.     for (int i = 0; i < vx.size(); i++)
  261.     {
  262.         if (i == 0 or vx[i].fi != vx[i - 1].fi)
  263.             ++cx;
  264.         a[vx[i].se].CX = cx;
  265.     }
  266.     for (int i = 0; i < vy.size(); i++)
  267.     {
  268.         if (i == 0 or vy[i].fi != vy[i - 1].fi)
  269.             ++cy;
  270.         a[vy[i].se].CY = cy;
  271.     }
  272. }
  273.  
  274. fami lore()
  275. {
  276.     if (fopen("starofhope.inp", "r"))
  277.     {
  278.         freefire("starofhope.inp", "r", stdin);
  279.         freefire("starofhope.out", "w", stdout);
  280.     }
  281.     SPED;
  282.     cin >> t;
  283.     while (t--)
  284.     {
  285.         cin >> m >> n >> p >> q;
  286.  
  287.         a[0] = {1, 1, 0, 0, 0, 0, 0};
  288.         for (int i = 1; i <= p; i++)
  289.         {
  290.             int N, E;
  291.             cin >> N >> E;
  292.             a[i] = {N, E, 0, 0, i, 0, 0};
  293.         }
  294.         a[p + 1] = {m, n, 0, 0, p + 1, 0, 0};
  295.  
  296.         for (int i = 1; i <= q; i++)
  297.         {
  298.             lint N, I, G, A;
  299.             cin >> N >> I >> G >> A;
  300.             b[i] = {N, I, G, A};
  301.         }
  302.  
  303.         compress();
  304.  
  305.         for (int i = 0; i <= p + 1; i++)
  306.         {
  307.             auto [idx, idy, cidx, cidy, id, idh, idc] = a[i];
  308.             adjh[cidx].emplace_back(idy, id);
  309.             adjc[cidy].emplace_back(idx, id);
  310.         }
  311.  
  312.         for (int i = 1; i <= p + 2; i++)
  313.         {
  314.             sort(adjh[i].begin(), adjh[i].end());
  315.             sort(adjc[i].begin(), adjc[i].end());
  316.         }
  317.  
  318.         for (int id = 1; id <= p + 2; id++)
  319.         {
  320.             for (int i = 0; i < adjh[id].size(); i++)
  321.             {
  322.                 auto [wc, idx] = adjh[id][i];
  323.                 a[idx].idH = i;
  324.             }
  325.             for (int i = 0; i < adjc[id].size(); i++)
  326.             {
  327.                 auto [wh, idx] = adjc[id][i];
  328.                 a[idx].idC = i;
  329.             }
  330.         }
  331.  
  332.         if (m <= 2000 and n <= 2000 and q > 10)
  333.         {
  334.             for (int i = 1; i <= q; ++i)
  335.             {
  336.                 auto [x1, y1, x2, y2] = b[i];
  337.                 ++dp[x1][y1];
  338.                 --dp[x2 + 1][y1];
  339.                 --dp[x1][y2 + 1];
  340.                 ++dp[x2 + 1][y2 + 1];
  341.             }
  342.  
  343.             for (int i = 1; i <= m + 1; ++i)
  344.                 for (int j = 1; j <= n + 1; ++j)
  345.                     dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
  346.  
  347.             for (int i = 1; i <= m; ++i)
  348.                 for (int j = 1; j <= n; ++j)
  349.                     dp[i][j] = (dp[i][j] > 0);
  350.  
  351.             for (int i = 1; i <= m; ++i)
  352.             {
  353.                 hpref[i][0] = 0;
  354.                 for (int j = 1; j <= n; ++j)
  355.                     hpref[i][j] = hpref[i][j - 1] + dp[i][j];
  356.             }
  357.  
  358.             for (int j = 1; j <= n; ++j)
  359.             {
  360.                 cpref[0][j] = 0;
  361.                 for (int i = 1; i <= m; ++i)
  362.                     cpref[i][j] = cpref[i - 1][j] + dp[i][j];
  363.             }
  364.  
  365.             dijkstra1();
  366.  
  367.             lint res = min(dist[0][p + 1], dist[1][p + 1]);
  368.  
  369.             cout << (res == INF ? -1 : res) << endl;
  370.  
  371.             reset1();
  372.         }
  373.  
  374.         else
  375.         {
  376.             dijkstra();
  377.  
  378.             lint res = min(dist[0][p + 1], dist[1][p + 1]);
  379.  
  380.             cout << (res == INF ? -1 : res) << endl;
  381.  
  382.             reset();
  383.         }
  384.     }
  385. }
  386. // Let your soul wander where dreams are born.
  387.  
Success #stdin #stdout 0.01s 14668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LAqokE
language:
C++14 (gcc 8.3)
created:
8 hours 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!