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 Data tuple<int, int, int, lint>
  16.  
  17. const lint INF = 0x1f1f1f1f1f1f1f1f;
  18. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  19.  
  20. using namespace std;
  21.  
  22. int n, m, s, t;
  23. vector<tuple<int, lint, int, int>> adj[50005];
  24. Data edge[50005];
  25. bool checksub1 = true;
  26. bool vis[50005];
  27. lint bef[50005];
  28.  
  29. int par[50005], sz[50005];
  30.  
  31. void setup()
  32. {
  33.     iota(par + 1, par + 1 + n, 1);
  34.     fill(sz + 1, sz + 1 + n, 1);
  35. }
  36.  
  37. int find_par(int now)
  38. {
  39.     return par[now] == now ? now : par[now] = find_par(par[now]);
  40. }
  41.  
  42. void combine(int l, int r)
  43. {
  44.     l = find_par(l);
  45.     r = find_par(r);
  46.  
  47.     if (l == r)
  48.         return;
  49.  
  50.     if (sz[l] < sz[r])
  51.         swap(l, r);
  52.  
  53.     par[r] = l;
  54.     sz[l] += sz[r];
  55. }
  56.  
  57. bool check1(lint mid)
  58. {
  59.     fill(vis, vis + 1 + n, false);
  60.     queue<int> temp;
  61.     vis[s] = true;
  62.     temp.emplace(s);
  63.  
  64.     while (!temp.empty())
  65.     {
  66.         auto now = temp.front();
  67.         temp.pop();
  68.         if (now == t)
  69.             return true;
  70.  
  71.         for (auto [v, w, mode, idx] : adj[now])
  72.         {
  73.             if (w <= mid and !vis[v])
  74.             {
  75.                 vis[v] = true;
  76.                 temp.emplace(v);
  77.             }
  78.         }
  79.     }
  80.  
  81.     return vis[t];
  82. }
  83.  
  84. lint binaryu1()
  85. {
  86.     lint l = 0, r = 1e9, mid, ans = -1;
  87.  
  88.     while (l <= r)
  89.     {
  90.         mid = l + r >> 1;
  91.  
  92.         if (check1(mid))
  93.         {
  94.             ans = mid;
  95.             r = mid - 1;
  96.         }
  97.  
  98.         else
  99.             l = mid + 1;
  100.     }
  101.  
  102.     return ans;
  103. }
  104.  
  105. void sub1()
  106. {
  107.     cout << binaryu1() << endl;
  108. }
  109.  
  110. bool legit[50005];
  111.  
  112. bool check2(lint mid)
  113. {
  114.     fill(vis, vis + 1 + n, false);
  115.     queue<int> q;
  116.     vis[s] = true;
  117.     q.emplace(s);
  118.  
  119.     while (!q.empty())
  120.     {
  121.         int u = q.front();
  122.         q.pop();
  123.         if (u == t)
  124.             return true;
  125.  
  126.         for (auto [v, w, mode, idx] : adj[u])
  127.         {
  128.             if (mode == 1)
  129.             {
  130.                 if (legit[idx] && !vis[v])
  131.                 {
  132.                     vis[v] = true;
  133.                     q.emplace(v);
  134.                 }
  135.             }
  136.             else
  137.             {
  138.                 if (w <= bef[mid] and !vis[v])
  139.                 {
  140.                     vis[v] = true;
  141.                     q.emplace(v);
  142.                 }
  143.             }
  144.         }
  145.     }
  146.     return vis[t];
  147. }
  148.  
  149. lint binaryu2(int mx)
  150. {
  151.     lint l = 1, r = mx, mid, ans = -1;
  152.     while (l <= r)
  153.     {
  154.         mid = l + r >> 1;
  155.         if (check2(mid))
  156.         {
  157.             ans = mid;
  158.             r = mid - 1;
  159.         }
  160.  
  161.         else
  162.             l = mid + 1;
  163.     }
  164.     return ans;
  165. }
  166.  
  167. vector<int> e1[50005], e2[50005];
  168.  
  169. void sub2()
  170. {
  171.     vector<lint> zip;
  172.  
  173.     for (int i = 1; i <= m; i++)
  174.         zip.emplace_back(get<3>(edge[i]));
  175.  
  176.     sort(zip.begin(), zip.end());
  177.     zip.erase(unique(zip.begin(), zip.end()), zip.end());
  178.  
  179.     for (int i = 1; i <= m; i++)
  180.     {
  181.         auto [mode, l, r, w] = edge[i];
  182.         auto idx = lower_bound(zip.begin(), zip.end(), w) - zip.begin() + 1;
  183.         bef[idx] = w;
  184.  
  185.         // cout << w << " : " << idx << endl;
  186.  
  187.         if (mode == 1)
  188.             e1[idx].emplace_back(i);
  189.  
  190.         else
  191.             e2[idx].emplace_back(i);
  192.     }
  193.  
  194.     int mxb = 0, stata = 0;
  195.  
  196.     setup();
  197.     for (int i = 1; i <= zip.size(); i++)
  198.     {
  199.         mxb = i;
  200.  
  201.         for (auto z : e2[i])
  202.         {
  203.             auto [mode, l, r, w] = edge[z];
  204.             combine(l, r);
  205.         }
  206.  
  207.         if (find_par(s) == find_par(t))
  208.             break;
  209.     }
  210.  
  211.     for (int i = 1; i <= zip.size(); i++)
  212.     {
  213.         if (find_par(s) == find_par(t))
  214.             break;
  215.         stata = i;
  216.  
  217.         for (auto z : e1[i])
  218.         {
  219.             auto [mode, l, r, w] = edge[z];
  220.             combine(l, r);
  221.         }
  222.     }
  223.  
  224.     lint res = INF;
  225.     for (int j = 1; j <= stata; j++)
  226.         for (auto z : e1[j])
  227.         {
  228.             auto [mode, l, r, w] = edge[z];
  229.             // combine(l, r);
  230.             legit[z] = true;
  231.         }
  232.  
  233.     int nwmxb = binaryu2(mxb);
  234.  
  235.     if (nwmxb != -1)
  236.         res = min(res, bef[nwmxb] + bef[stata]);
  237.  
  238.     for (int i = stata + 1; i <= zip.size(); i++)
  239.     {
  240.         for (auto z : e1[i])
  241.         {
  242.             legit[z] = true;
  243.             auto [mode, l, r, w] = edge[z];
  244.             // combine(l, r);
  245.         }
  246.         nwmxb = binaryu2(mxb);
  247.         mxb = nwmxb;
  248.  
  249.         res = min(res, bef[i] + bef[nwmxb]);
  250.     }
  251.     cout << res << endl;
  252. }
  253.  
  254. fami lore()
  255. {
  256.     SPED;
  257.     cin >> n >> m >> s >> t;
  258.  
  259.     for (int i = 1; i <= m; i++)
  260.     {
  261.         int mode, l, r;
  262.         lint w;
  263.         cin >> mode >> l >> r >> w;
  264.         adj[l].emplace_back(r, w, mode, i);
  265.         adj[r].emplace_back(l, w, mode, i);
  266.         edge[i] = {mode, l, r, w};
  267.  
  268.         if (mode == 2)
  269.             checksub1 = false;
  270.     }
  271.  
  272.     if (checksub1 == true)
  273.     {
  274.         sub1();
  275.         return 0;
  276.     }
  277.  
  278.     else if (n <= 5000 and m <= 5000)
  279.     {
  280.         sub2();
  281.         return 0;
  282.     }
  283.  
  284.     // else
  285.     // {
  286.     //     sub3();
  287.     //     return 0;
  288.     // }
  289. }
  290. // Let your soul wander where dreams are born.
  291.  
  292. /*
  293.     test sub1 :
  294.  
  295.     5 5 1 5
  296.  
  297.     1 1 2 2
  298.     1 2 3 4
  299.     1 3 4 3
  300.     1 2 4 5
  301.     1 4 5 2
  302.  
  303.     test sub2 :
  304.     6 7 1 4
  305.  
  306.     1 1 2 4
  307.     2 2 3 7
  308.     1 3 4 6
  309.     2 1 6 5
  310.     1 6 5 5
  311.     2 5 4 8
  312.     2 2 5 2
  313. */
  314.  
Success #stdin #stdout 0.01s 9248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6tNI3Q
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!