fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #pragma GCC optimize("O2")
  8. #define fi first
  9. #define se second
  10. #define M 1000000007
  11. #define MAXN 1000001
  12. #define INF 1000000000000
  13. #define BLOCK_SIZE 425
  14. #define MAX_NODE 1001001
  15. #define LOG 19
  16. #define ALPHA_SIZE 26
  17. #define BASE 311
  18. #define NAME "file"
  19. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  20. using namespace std;
  21. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  22. const ll NMOD = 1;
  23. const int dx[] = {-1, 0, 1,0};
  24. const int dy[] = {0, 1, 0, -1};
  25. //**Variable**//
  26. ll n , ans, m  ;
  27. ll arr[MAXN];
  28. ll res[MAXN] ;
  29. ll lab[MAXN]  ;
  30. pair<ll,ll> edge[MAXN]  ;
  31. //**Struct**//
  32.  
  33. //**Function**//
  34. ll find_set(ll a ) {
  35. return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  36. }
  37. void union_set(ll a , ll b ) {
  38. a = find_set(a) ;
  39. b = find_set(b) ;
  40. if(a == b ) return ;
  41. if(lab[a] > lab[b])swap(a , b) ;
  42. ll sz_a = -lab[a] , sz_b = - lab[b] ;
  43. lab[a] += lab[b] ;
  44. lab[b] = a ;
  45. ans =ans  - (n - sz_a) * sz_a  - (n - sz_a - sz_b ) * sz_b + (sz_a + sz_b) *(n - sz_a - sz_b) ;
  46. }
  47. void init() {
  48.     cin>>n >> m ;
  49.     memset(lab , -1 , sizeof lab) ;
  50.     ans = n * (n - 1) /2;
  51.     for(ll i = 1 ; i <= m ; i ++ )cin>>edge[i].fi >> edge[i].se  ;
  52. }
  53.  
  54. void solve() {
  55.  
  56. for(ll i = m ; i >=  1 ; i -- ) {
  57.     res[i] = ans ;
  58.     union_set(edge[i].fi , edge[i].se ) ;
  59. }
  60. for(ll i = 1 ; i <= m ; i ++ ) cout<<res[i] << el;
  61. }
  62.  
  63. __ROOT__ {
  64. //     freopen(NAME".inp" , "r" , stdin);
  65. //     freopen(NAME".out" , "w", stdout) ;
  66.     fast;
  67.     init();
  68.     solve();
  69. }
  70.  
  71.  
  72.  
  73.  
Success #stdin #stdout 0.01s 13748KB
comments (?)
stdin
copy 
 5 6
 2 3
 3 4
 1 4
 3 5
 2 4
 1 2
stdout
copy 
0
6
6
7
9
10
https://ideone.com/ew1Dd4
language:
C++14 (gcc 8.3)
created:
233 days ago
visibility:
secret

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!