Advertisement
cs-mshah

Untitled

Jan 23rd, 2022
645
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problem: E. We Need More Bosses
  2. // Contest: Codeforces - Educational Codeforces Round 46 (Rated for Div. 2)
  3. // URL: https://codeforces.com/problemset/problem/1000/E
  4. // Memory Limit: 256 MB
  5. // Time Limit: 2000 ms
  6.  
  7. /*
  8.  
  9. WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!
  10.  
  11. Falling down is an accident, Staying down is a choice.
  12.  
  13. */
  14. #pragma GCC optimize("O3,unroll-loops")
  15. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  16.  
  17. #include "bits/stdc++.h"
  18. /*#include <ext/pb_ds/assoc_container.hpp>
  19. #include <ext/pb_ds/tree_policy.hpp>*/
  20.  
  21. using namespace std;
  22. //using namespace __gnu_pbds;
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26. typedef pair<ll,ll> pll;
  27. typedef vector<bool> vb;
  28. typedef vector<int> vi;
  29. typedef vector<ll> vll;
  30. typedef vector<vi> vvi;
  31. typedef vector<vb> vvb;
  32. typedef vector<vll> vvll;
  33. typedef vector<pll> vpll;
  34. typedef vector<string> vs;
  35. typedef unordered_map<ll,ll> umll;
  36. template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
  37. /*template <typename num_t>
  38. using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;*/
  39. // find_by_order(k): iterator to the kth largest(0 indexed). order_of_key(k): no. of items < k
  40.  
  41. #define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
  42. #define FOR3(i,a,b) for(long long i=a;i<b;i++)
  43. #define FOR4(i,a,b,step) for(long long i=a;i<b;i=i+step)
  44. #define REV3(i,a,b) for(long long i=a;i>=b;i--)
  45. #define REV4(i,a,b,step) for(long long i=a;i>=b;i=i-step)
  46. #define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3)(__VA_ARGS__)
  47. #define REV(...) GET_MACRO(__VA_ARGS__, REV4, REV3)(__VA_ARGS__)
  48. #define F first
  49. #define S second
  50. #define pb push_back
  51. #define ub upper_bound
  52. #define lb lower_bound
  53. #define all(v) v.begin(),v.end()
  54. #define rall(v) v.rbegin(),v.rend()
  55. #define tc ll tests;cin>>tests;while(tests--)
  56. #define io ios_base::sync_with_stdio(false);cin.tie(nullptr);
  57. #define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
  58. #define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
  59. #define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
  60. #define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
  61. #define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
  62. #define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
  63. #define pyes(CONDITION) cout << (CONDITION ? "YES" : "NO") << '\n';
  64. #define newl cout<<"\n"
  65. #define MOD 1000000007
  66. #define INF LLONG_MAX/2
  67. #define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
  68. #define m2(x) (int[]){(x forward<U>(b),0)...}
  69. m1(pr) { cout << forward<T>(a);  m2(cout << " " <<); cout << "\n"; }
  70. m1(re) { cin >> forward<T>(a); m2(cin >>); }
  71. template <class ...Args>
  72. auto &readd(Args &...args) { return (cin >> ... >> args); }
  73. #define re(...) __VA_ARGS__; readd(__VA_ARGS__)
  74.  
  75. const ll dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
  76. // const ll dx[8] = {-2,-1,1,2,2,1,-1,-2}, dy[8] = {1,2,2,1,-1,-2,-2,-1}; //knight moves
  77.  
  78. // ************************DEBUG START********************************
  79. // #ifndef ONLINE_JUDGE
  80. // //#define cerr cout
  81. // #include "myprettyprint.hpp"
  82. // #else
  83. // #define dbg(...)
  84. // #endif
  85. // ************************DEBUG END**********************************
  86.  
  87. constexpr ll pct(ll x) { return __builtin_popcountll(x); } // # of bits set
  88. constexpr ll bits(ll x) {return x == 0LL ? 0LL : 63LL-__builtin_clzll(x); } // floor(log2(x))
  89. constexpr ll p2(ll x) { return 1LL<<x; }
  90. constexpr ll msk2(ll x) { return p2(x)-1LL; }
  91. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  92.  
  93. vvll g, adj;
  94. ll bridges = 0, cnt = 0;
  95. vll dp, lev, id;
  96. vb vis;
  97. map<pll, bool> edge;
  98.  
  99. void dfs(vvll &g, ll u, ll p=-1)
  100. {
  101.     for(auto v:g[u])
  102.     {
  103.         if(lev[v]==0) // edge to child
  104.         {
  105.             lev[v] = lev[u] + 1;
  106.             dfs(g, v, u);
  107.             dp[u] += dp[v];
  108.         }
  109.         else if(lev[v] < lev[u]) // edge up
  110.         {
  111.             dp[u]++;
  112.         }
  113.         else if(lev[v] > lev[u]) // edge down
  114.         {
  115.             dp[u]--;
  116.         }
  117.     }
  118.     dp[u]--; // parent also counted
  119.  
  120.     if(lev[u]>1 && dp[u]==0)
  121.     {
  122.         bridges++;
  123.         edge[{u,p}] = true;
  124.         edge[{p,u}] = true;
  125.     }
  126. }
  127.  
  128. void dfs1(ll u)
  129. {
  130.     vis[u] = true;
  131.     id[u] = cnt;
  132.     for(auto v:g[u])
  133.     {
  134.         if(vis[v] || edge.count({u,v})) continue;
  135.         dfs1(v);
  136.     }
  137. }
  138.  
  139. void test()
  140. {
  141.     ll re(n,m);
  142.     g.resize(n);
  143.     dp.resize(n);
  144.     lev.resize(n);
  145.     id.resize(n);
  146.     vis.resize(n);
  147.     FOR(i,0,m)
  148.     {
  149.         ll re(u,v);
  150.         g[--u].pb(--v);
  151.         g[v].pb(u);
  152.     }
  153.    
  154.     dfs(g, 0);
  155.    
  156.     FOR(i,0,n)
  157.     {
  158.         if(!vis[i])
  159.         {
  160.             dfs1(i);
  161.             cnt++;
  162.         }
  163.     }
  164.    
  165.     adj.resize(cnt);
  166.     FOR(u,0,n)
  167.     {
  168.         for(auto v:g[u])
  169.         {
  170.             if(id[u]!=id[v])
  171.             {
  172.                 adj[id[u]].pb(id[v]);
  173.             }
  174.         }
  175.     }
  176.    
  177.     lev.assign(cnt,0);
  178.     dfs(adj, 0);
  179.     ll u = max_element(all(lev)) - lev.begin();
  180.     lev.assign(cnt,0);
  181.     dfs(adj, u);
  182.     pr(*max_element(all(lev)));
  183. }
  184.  
  185. int main()
  186. {
  187.     io;
  188.     ll tests=1;
  189.     //cin>>tests;
  190.     while(tests--)
  191.     {
  192.         test();
  193.     }
  194.     return 0;
  195. }
  196.  
  197.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement