Advertisement
konchin_shih

c495

Feb 5th, 2021
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.21 KB | None | 0 0
  1. //Input Output
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<fstream>
  5. #include<sstream>
  6. #include<streambuf>
  7. //C lib
  8. #include<cstdlib>
  9. #include<cstring>
  10. #include<cmath>
  11. #include<climits>
  12. #include<cctype>
  13. //Container
  14. #include<array>
  15. #include<vector>
  16. #include<stack>
  17. #include<queue>
  18. #include<deque>
  19. #include<list>
  20. #include<bitset>
  21. #include<set>
  22. #include<map>
  23. #include<unordered_set>
  24. #include<unordered_map>
  25. //Others
  26. #include<tuple>
  27. #include<algorithm>
  28. #include<functional>
  29. #include<numeric>
  30. #include<iterator>
  31. #include<limits>
  32. #include<utility>
  33. #include<complex>
  34. #include<type_traits>
  35. #include<initializer_list>
  36. #include<random>
  37.  
  38. using namespace std;
  39.  
  40. void _debug() {cerr << '\n';}
  41. template <typename A, typename... B>
  42. void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
  43. #define debug(...) cerr << '(' << (#__VA_ARGS__) << ") : ", _debug(__VA_ARGS__)
  44.  
  45. namespace abb {
  46. using ll = long long;
  47. using uint = unsigned int;
  48. using ull = unsigned long long;
  49. template<typename T> using V = vector<T>;
  50. template<typename T> using Q = queue<T>;
  51. template<typename T> using DQ = deque<T>;
  52. template<typename T> using V2d = vector<vector<T>>;
  53. template<typename T> using US = unordered_set<T>;
  54. template<typename T, size_t s> using A = array<T, s>;
  55. template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
  56. template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
  57. template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
  58. template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
  59. template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
  60. template<typename T> using F = function<T>;
  61. }
  62.  
  63. namespace output {
  64. template<typename T1, typename T2>
  65. inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  66.     return os << '(' << p.first << ", " << p.second << ')';
  67. }
  68. #define unfold1(Container) \
  69. template<typename T> \
  70. inline ostream& operator<<(ostream& os, const Container<T>& x) { \
  71.     for (const auto& i : x) \
  72.         os << i << ' '; \
  73.     return os; \
  74. }
  75. #define unfold2(Container) \
  76. template<typename T1,typename T2> \
  77. inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
  78.     for (const auto& i : x) \
  79.         os << i << ' '; \
  80.     return os; \
  81. }
  82. unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
  83. #undef unfold1
  84. #undef unfold2
  85. };
  86.  
  87. namespace rit {
  88. struct fast_istream {
  89.     operator bool() const {return bool(cin);}
  90.     fast_istream() {cin.tie(nullptr);}
  91. } fin;
  92. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  93. fast_istream & operator>>(fast_istream& is, T& n) {
  94.     while (isspace(cin.rdbuf()->sgetc()))
  95.         cin.rdbuf()->snextc();
  96.     bool sign = false;
  97.     if (cin.rdbuf()->sgetc() == '-')
  98.         sign = true, cin.rdbuf()->snextc();
  99.     for (n = 0; isdigit(cin.rdbuf()->sgetc());)
  100.         n *= 10, n += cin.rdbuf()->sbumpc() - '0';
  101.     n = sign ? -n : n;
  102.     return is;
  103. }
  104. fast_istream& operator>>(fast_istream& is, char& n) {
  105.     while (isspace(cin.rdbuf()->sgetc()))
  106.         cin.rdbuf()->snextc();
  107.     n = cin.rdbuf()->sbumpc();
  108.     return is;
  109. }
  110. }
  111.  
  112. #define endl '\n'
  113. namespace wit {
  114. struct fast_ostream {
  115.     operator bool() const {return bool(cout);}
  116.     fast_ostream() {cout.tie(nullptr);}
  117. } fout;
  118. constexpr int buffer_size = 30;
  119. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  120. fast_ostream & operator<<(fast_ostream& os, T n) {
  121.     if (!n) {cout.rdbuf()->sputc('0'); return os;}
  122.     if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
  123.     static char buffer[buffer_size];
  124.     int cnt = buffer_size;
  125.     for (; n; n /= 10)
  126.         buffer[--cnt] = n % 10 + '0';
  127.     cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
  128.     return os;
  129. }
  130. fast_ostream& operator<< (fast_ostream& os, const char& n) {
  131.     cout.rdbuf()->sputc(n); return os;
  132. }
  133. }
  134.  
  135. //#define MULTI_TASKCASE
  136. using namespace abb;
  137. using namespace output;
  138. using namespace rit;
  139. using namespace wit;
  140.  
  141. inline void init() {
  142.  
  143. }
  144.  
  145. struct node {int b; ll w; node(int x, ll y): b(x), w(y) {}};
  146. bool operator<(node a, node b) {
  147.     return a.w > b.w;
  148. }
  149. bool operator==(node a, node b) {
  150.     return a.b == b.b && a.w == b.w;
  151. }
  152.  
  153. inline void solve() {
  154.     int n, m;
  155.     cin >> n >> m;
  156.     V<V<node>> edge(n), mst(n);
  157.     while (m--) {
  158.         static ll a, b, w;
  159.         cin >> a >> b >> w, a--, b--;
  160.         edge[a].emplace_back(b, w);
  161.         edge[b].emplace_back(a, w);
  162.     }
  163.     V<ll> d(n, 1e15);
  164.     V<int> p(n, -1);
  165.     V<bool> vis(n, false);
  166.     PQ<node> pq;
  167.     pq.emplace(0, p[0] = d[0] = 0);
  168.     for (int k = 0; k < n; k++) {
  169.         static int a; a = ~0u;
  170.         while (pq.size() && vis[a = pq.top().b]) pq.pop();
  171.         if (!~a) break;
  172.         vis[a] = true;
  173.         for (const auto& i : edge[a])
  174.             if (!vis[i.b] && i.w < d[i.b])
  175.                 pq.emplace(i.b, d[i.b] = i.w), p[i.b] = a;
  176.     }
  177.     ll mstp = accumulate(d.begin(), d.end(), 0LL);
  178.     cout << mstp << ' ';
  179.     for (int i = 1; i < n; i++) {
  180.         mst[p[i]].emplace_back(i, d[i]);
  181.         static int a, b; static ll w;
  182.         a = p[i], b = i, w = d[i];
  183.         edge[a].erase(find(edge[a].begin(), edge[a].end(), node(b, w)));
  184.         edge[b].erase(find(edge[b].begin(), edge[b].end(), node(a, w)));
  185.     }
  186.     V<V<node>> v(n, V<node>(__lg(n) + 1, {0, 0}));
  187.     V<int> tin(n), tout(n);
  188.     F<void(int, int, int)> build = [&](int cur, int pre, ll wt) {
  189.         static int t = 0;
  190.         tin[cur] = t++;
  191.         for (int i = 0, k = pre; i <= __lg(n); i++) {
  192.             v[cur][i].b = k, v[cur][i].w = max(v[cur][i].w, wt);
  193.             wt = v[k][i].w, k = v[k][i].b;
  194.         }
  195.         for (const auto& i : mst[cur])
  196.             if (i.b != pre) build(i.b, cur, i.w);
  197.         tout[cur] = t++;
  198.     };
  199.     auto isanc = [&](int a, int b) {
  200.         return tin[a] <= tin[b] && tout[a] >= tout[b];
  201.     };
  202.     auto maxp = [&](int a, int b) {
  203.         int x = a, y = b;
  204.         ll ret = 0;
  205.         if (a == b) return ret;
  206.         for (int i = __lg(n); i >= 0; i--) {
  207.             if (!isanc(v[x][i].b, b)) ret = max(ret, v[x][i].w), x = v[x][i].b;
  208.             if (!isanc(v[y][i].b, a)) ret = max(ret, v[y][i].w), b = v[y][i].b;
  209.         }
  210.         if (!isanc(x, b)) ret = max(ret, v[x][0].w);
  211.         if (!isanc(y, a)) ret = max(ret, v[y][0].w);
  212.         return ret;
  213.     };
  214.     build(0, 0, 0);
  215.     ll diff = 1e18;
  216.     for (int a = 0; a < n; a++)
  217.         for (const auto& i : edge[a])
  218.             diff = min(diff, i.w - maxp(a, i.b));
  219.     cout << mstp + diff << endl;
  220. }
  221.  
  222. main() {
  223.     ios::sync_with_stdio(false);
  224.     init();
  225.     int t = 1;
  226. #ifdef MULTI_TASKCASE
  227.     cin >> t; cin.ignore();
  228. #endif
  229.     while (t--) solve();
  230.     return 0;
  231. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement