fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define endl '\n'
  6. #define pi pair<int,int>
  7. #define adjs(name, type, size) vector<vector<type>>name(size)
  8. #define adjpass(name, type) vector<vector<type>>&name
  9. #define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
  10. int cases = 1;
  11.  
  12. int timer = 1;
  13. set<pi > bridges;
  14.  
  15. void dfsSCC(int node, int dad, vector<int> &dfn, vector<int> &lowlink, adjpass(v, int)) {
  16.     dfn[node] = lowlink[node] = timer++;
  17.     for (auto i: v[node]) {
  18.         if (i == dad)
  19.             continue;
  20.         if (dfn[i] == -1) { //not vis
  21.             dfsSCC(i, node, dfn, lowlink, v);
  22.             lowlink[node] = min(lowlink[node], lowlink[i]);
  23.             if (lowlink[i] > dfn[node]) {
  24.                 bridges.insert({min(node, i), max(node, i)});
  25.             }
  26.         } else {
  27.             lowlink[node] = min(lowlink[node], dfn[i]);
  28.         }
  29.     }
  30. }
  31.  
  32. void dfs(int node, vector<set<pi >> &v, vector<int> &vis, int &last, int &mx, int cur) {
  33.     vis[node] = 1;
  34.     if (cur > mx) {
  35.         mx = cur;
  36.         last = min(last, node);
  37.         last = node;
  38.     } else if (cur == mx) {
  39.         last = min(last, node);
  40.     }
  41.     for (auto i: v[node]) {
  42.         if (!vis[i.first]) {
  43.             dfs(i.first, v, vis, last, mx, cur + i.second);
  44.         }
  45.     }
  46. }
  47.  
  48. class DSU {
  49. private:
  50.     vector<int> rank, par, size;
  51. public:
  52.     DSU(int n = 0) {
  53.         rank.resize(n + 1);
  54.         par.resize(n + 1);
  55.         size.resize(n + 1, 1);
  56.         for (int i = 0; i <= n; i++)
  57.             par[i] = i;
  58.     }
  59.  
  60.     int findUpar(int node) {
  61.         if (node == par[node])
  62.             return node;
  63.         return par[node] = findUpar(par[node]);//path comp
  64.     }
  65.  
  66.     void unionbyRank(int u, int v) {
  67.         int UparU = findUpar(u);
  68.         int UparV = findUpar(v);
  69.         if (UparU == UparV)
  70.             return;
  71.         if (rank[UparU] < rank[UparV]) {
  72.             par[UparU] = UparV;
  73.         } else {
  74.             par[UparV] = UparU;
  75.             rank[UparU] += (rank[UparU] == rank[UparV]);
  76.         }
  77.     }
  78.  
  79.     void unionbySize(int u, int v) {
  80.         int UparU = findUpar(u);
  81.         int UparV = findUpar(v);
  82.         if (UparU == UparV)
  83.             return;
  84.         if (size[UparU] < size[UparV]) {
  85.             par[UparU] = UparV;
  86.             size[UparV] += size[UparU];
  87.         } else {
  88.             par[UparV] = UparU;
  89.             size[UparU] += size[UparV];
  90.         }
  91.     }
  92. };
  93.  
  94. void gon() {
  95.     int n, m;
  96.     cin >> n >> m;
  97.     adjs(v, int, n + 5);
  98.     vector<pair<pi, int> > ed;
  99.     for (int i = 0; i < m; i++) {
  100.         int l, r, c;
  101.         cin >> l >> r >> c;
  102.         ed.push_back({{min(l, r), max(l, r)}, c});
  103.         v[l].push_back(r);
  104.         v[r].push_back(l);
  105.     }
  106.     vector<int> dfn(n + 5, -1), lowlink(n + 5, -1);
  107.     timer = 1;
  108.     bridges.clear();
  109.     for (int i = 1; i <= n; i++) {
  110.         if (dfn[i] == -1) {
  111.             dfsSCC(i, -1, dfn, lowlink, v);
  112.         }
  113.     }
  114.     map<pi, int> mp;
  115.     for (auto i: bridges)
  116.         mp[i] = 1;
  117.     for (auto &i: ed) {
  118.         if (!mp.count(i.first))
  119.             i.second = 0;
  120.     }
  121.     DSU d(n + 5);
  122.     for (auto i: ed) {
  123.         if (i.second == 0) {
  124.             d.unionbySize(i.first.first, i.first.second);
  125.         }
  126.     }
  127.     vector<int> comp(n + 5, 1e9);
  128.     for (int i = 1; i <= n; i++) {
  129.         comp[d.findUpar(i)] = min(comp[d.findUpar(i)], i);
  130.     }
  131.     vector<set<pi >> mst(n + 5);
  132.     for (auto i: ed) {
  133.         if (i.second == 0) {
  134.             continue;
  135.         }
  136.         int a = comp[d.findUpar(i.first.first)];
  137.         int b = comp[d.findUpar(i.first.second)];
  138.         mst[a].insert({b, i.second});
  139.         mst[b].insert({a, i.second});
  140.     }
  141.     int St = 1;
  142.     int last = 1;
  143.     int mx = 0;
  144.     int cur = 0;
  145.     vector<int> vis(n + 5);
  146.     dfs(St, mst, vis, last, mx, cur);
  147.     vis.assign(n + 5, 0);
  148.     int L = last;
  149.     St = last;
  150.     mx = 0;
  151.     cur = 0;
  152.     dfs(St, mst, vis, last, mx, cur);
  153.     int R = last;
  154.     vector<pi > dad(n + 5, {-1, -1});
  155.     vector<int> dis(n + 5, 1e18);
  156.     dis[last] = 0;
  157.     priority_queue<pi > pq;
  158.     pq.push({0, -last});
  159.     while (pq.size()) {
  160.         auto [cost, node] = pq.top();
  161.         node *= -1;
  162.         pq.pop();
  163.         if (cost > dis[node])
  164.             continue;
  165.         for (auto i: mst[node]) {
  166.             if (cost + i.second < dis[i.first]) {
  167.                 dad[i.first] = {node, i.second};
  168.                 dis[i.first] = cost + i.second;
  169.                 pq.push({dis[i.first], -i.first});
  170.             }
  171.         }
  172.     }
  173.     int Node = L;
  174.     vector<int> path;
  175.     vector<int> vals;
  176.     vals.push_back(0);
  177.     int sum = 0;
  178.     while (dad[L].first != -1) {
  179.         sum += dad[L].second;
  180.         vals.push_back(dad[L].second);
  181.         path.push_back(L);
  182.         L = dad[L].first;
  183.     }
  184.     path.push_back(L);
  185.     int ansNode = path[0], mxcost = sum, pre = 0;
  186.     for (int i = 0; i < vals.size(); i++) {
  187.         pre += vals[i];
  188.         sum -= vals[i];
  189.         int mxcur = max(pre, sum);
  190.         if (mxcur < mxcost) {
  191.             mxcost = mxcur;
  192.             ansNode = path[i];
  193.         } else if (mxcur == mxcost) {
  194.             ansNode = min(ansNode, path[i]);
  195.         }
  196.     }
  197.     cout << ansNode << " " << mxcost << endl;
  198. }
  199.  
  200. int32_t main() {
  201.     killua;
  202.     int t = 1;
  203.     if (cases) cin >> t;
  204.     while (t--) {
  205.         gon();
  206.     }
  207. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0
https://ideone.com/YWFnn9
language:
C++14 (gcc 8.3)
created:
46 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!