#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
const ll mod=1000000007;
const int N=100005;
int n,m;
struct UF{
int p[N]={0};
ll ans=0,sz[N],szIn[N];
set<int> in[N],out[N],inV[N],S[N];
void init(){
for(int i=1;i<=n;i++){
sz[i]=1;
szIn[i]=0;
S[i].emplace(i);
}
}
int Find(int u){
if(!p[u]) return u;
return p[u]=Find(p[u]);
}
void add(int u,int v){
int Gu=Find(u),Gv=Find(v);
if(Gu==Gv) return;
if(in[Gu].count(Gv)){
ans+=2*sz[Gu]*sz[Gv];
ans-=sz[Gu]*inV[Gu].size();
ans-=sz[Gv]*inV[Gv].size();
//debug(ans,sz[Gu],sz[Gv],inV[Gu],inV[Gv]);
if(in[Gu].size()+out[Gu].size()+inV[Gu].size()+S[Gu].size()<in[Gv].size()+out[Gv].size()+inV[Gv].size()+S[Gv].size()) swap(Gu,Gv);
for(int Gw: in[Gv]){
out[Gw].erase(Gv);
out[Gw].emplace(Gu);
in[Gu].emplace(Gw);
}
for(int Gw: out[Gv]){
in[Gw].erase(Gv);
in[Gw].emplace(Gu);
out[Gu].emplace(Gw);
}
for(int w: inV[Gv]){
if(!S[Gu].count(w)) inV[Gu].emplace(w);
//else ans+=sz[Gv];
}
for(int w: S[Gv]){
S[Gu].emplace(w);
if(inV[Gu].count(w)){
//ans+=sz[Gu];
inV[Gu].erase(w);
}
}
sz[Gu]+=sz[Gv];
ans+=sz[Gu]*inV[Gu].size();
//debug(ans,Gu,inV[Gu]);
p[Gv]=Gu;
} else if(!in[Gv].count(u)){
ans+=sz[Gv];
in[Gv].emplace(Gu);
out[Gu].emplace(Gv);
inV[Gv].emplace(u);
}
}
}U;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
U.init();
for(int u,v,i=1;i<=m;i++){
cin>>u>>v;
U.add(u,v);
cout<<U.ans<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21080 KB |
Output is correct |
| 2 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21080 KB |
Output is correct |
| 2 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21080 KB |
Output is correct |
| 2 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
