fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /* nichijou */
  4. template<class T,class U>
  5. bool cmax(T & a, const U & b) {return a < b ? a = b, 1 : 0;}
  6. template<class T,class U>
  7. bool cmin(T & a, const U & b) {return b < a ? a = b, 1 : 0;}
  8. /* data type */
  9. typedef long long ll;
  10. typedef pair<int,int> pii;
  11. typedef pair<ll,ll> pll;
  12. #define F first
  13. #define S second
  14. /* STL container */
  15. typedef vector<int> vi;
  16. typedef vector<ll> vll;
  17. #define SZ(a) ((int)(a).size())
  18. #define ALL(a) begin(a), end(a)
  19. #define CLR(a) (a).clear()
  20. #define BK(a) ((a).back())
  21. #define FT(a) ((a).front())
  22. #define DB(a) (a).pop_back()
  23. #define DF(a) (a).pop_front()
  24. #define PB push_back
  25. #define EB emplace_back
  26. /* I gave you my heart and then you turned around. */
  27. void _BG(const char * s) {cerr<<s<<endl;}
  28. template<class T, class ... TT>
  29. void _BG(const char * s,T a, TT...b)
  30. {
  31.     for (size_t c = 0; *s && (c || *s != ','); cerr << *s++)
  32.         c += count(ALL("([{"),*s) - count(ALL(")]}"),*s);
  33.     cerr << " = " << a;
  34.     if (*s) {
  35.         cerr << ", ";
  36.         ++s;
  37.     }
  38.     _BG(s,b...);
  39. }
  40. #ifdef PR3PONY
  41. #define BG(...) do { \
  42.     cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
  43.     _BG(#__VA_ARGS__,__VA_ARGS__); \
  44. } while(0)
  45. #else
  46. #define BG(...)
  47. #endif
  48. /* Good Luck && Have Fun ! */
  49. const int N = 2e5 +87;
  50. int n, m;
  51. vector<array<int, 3>> e;
  52. vector<int> g[N];
  53. int d[N], p[N], cc;
  54. int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
  55. void meld(int a, int b)
  56. {
  57.     a = find(a), b = find(b);
  58.     if (a == b)
  59.         return;
  60.     --cc;
  61.     p[b] = a;
  62. }
  63. void check()
  64. {
  65.     cerr << "========\n";
  66.     cerr << "d:";
  67.     for (int i = 1; i <= n; ++i)
  68.         cerr << ' ' << d[i];
  69.     cerr << endl;
  70.     cerr << "edges: \n";
  71.     for (int i = 1; i < n; ++i)
  72.         for (int x : g[i]) {
  73.             int j = e[x][0] ^ e[x][1] ^ i;
  74.             if (j > i)
  75.                 cerr << i << ' ' << j << ' ' << e[x][2] << endl;
  76.         }
  77.     assert(is_sorted(d + 1, d + n + 1));
  78.     deque<int> q = {1};
  79.     vector<int> dis(n + 1, N);
  80.     dis[1] = 0;
  81.     while (q.size()) {
  82.         int u = q.front();
  83.         q.pop_front();
  84.         for (int i : g[u]) {
  85.             int v = e[i][0] ^ e[i][1] ^ u;
  86.             int w = dis[u] + e[i][2];
  87.             if (w < dis[v]) {
  88.                 dis[v] = w;
  89.                 if (e[i][2])
  90.                     q.push_back(v);
  91.                 else
  92.                     q.push_front(v);
  93.             }
  94.         }
  95.     }
  96.     for (int i = 1; i <= n; ++i)
  97.         assert(dis[i] == d[i]);
  98. }
  99. int main()
  100. {
  101.     ios::sync_with_stdio(0);
  102.     cin.tie(0);
  103.     cin >> n >> m;
  104.     for  (int i = 0; i < m; ++i) {
  105.         int u, v;
  106.         cin >> u >> v;
  107.         g[u].push_back(e.size());
  108.         g[v].push_back(e.size());
  109.         e.push_back({u, v, 1});
  110.     }
  111.     fill_n(d, n + 1, N);
  112.     d[1] = 0;
  113.     vector<int> q = {1}, nq;
  114.     int mx = 1;
  115.     cc = 1;
  116.     p[1] = 1;
  117.     int ptr = 2;
  118.     for (int k = 0; q.size(); ++k) {
  119.         while (p[ptr])
  120.             ++ptr;
  121.         while (!(ptr == mx + 1 && cc == 1)) {
  122.             d[ptr] = k;
  123.             mx = max(mx, ptr);
  124.             q.push_back(ptr);
  125.             p[ptr] = ptr;
  126.             ++cc;
  127.             for (int i : g[ptr]) {
  128.                 int v = e[i][0] ^ e[i][1] ^ ptr;
  129.                 if (p[v]) {
  130.                     e[i][2] = 0;
  131.                     meld(v, ptr);
  132.                 }
  133.             }
  134.             while (p[ptr])
  135.                 ++ptr;
  136.         }
  137.  
  138.         nq.clear();
  139.         for (int u : q) {
  140.             for (int i : g[u]) {
  141.                 int v = e[i][0] ^ e[i][1] ^ u;
  142.                 if (d[v] != N)
  143.                     continue;
  144.                 d[v] = k + 1;
  145.                 mx = max(mx, v);
  146.                 ++cc, p[v] = v;
  147.                 meld(v, u);
  148.                 nq.push_back(v);
  149.             }
  150.         }
  151.         swap(q, nq);
  152.     }
  153.     //for (int i = 1; i <= n; ++i) cerr << d[i] << " "; cerr << endl;
  154.     ll ans = 0;
  155.     for  (int i = 1; i <= n; ++i) {
  156.         ans += d[i];
  157.     }
  158.     cout << ans << endl;
  159.     check();
  160. }
  161.  
  162.  
Success #stdin #stdout #stderr 0s 8268KB
comments (?)
stdin
copy 
6 6
1 3
3 4
4 5
5 2
4 6
6 2
stdout
copy 
6
stderr
copy 
========
d: 0 1 1 1 1 2
edges: 
1 3 1
2 5 0
2 6 1
3 4 0
4 5 0
4 6 1
https://ideone.com/nGKkfd
language:
C++14 (gcc 8.3)
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!