#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100050;
const bool DEBUG=0;
int n,m,a,b,par[N],sz[N],inord[N],ans;
map<int,int> one[N],frm[N];
int find(int u){
return par[u]=(par[u]==u?u:find(par[u]));
}
signed main(){
cin>>n>>m;
iota(par+1,par+n+1,1);
for (int i=1;i<=n;i++) sz[i]=1;
while (m--){
cin>>a>>b;
if (DEBUG) cout<<a<<"->"<<b<<"\n";
if (find(a)==find(b)||one[find(b)][a]){
if (DEBUG) cout<<"ignore\n";
//alr have a->b edge
}else if (frm[find(a)][find(b)]){
//union find(a) and find(b)
if (DEBUG) cout<<"merge "<<find(a)<<" "<<find(b)<<"\n";
a=find(a);
b=find(b);
if (DEBUG) cout<<"size "<<sz[a]<<" "<<sz[b]<<" frm "<<frm[a][b]<<"\n";
if (DEBUG) cout<<"inord "<<inord[a]<<" "<<inord[b]<<"\n";
ans+=sz[a]*sz[b]*2;
ans-=sz[a]*frm[a][b];
inord[a]-=frm[a][b];
frm[a].erase(b);
ans-=inord[a]*sz[a];
ans-=inord[b]*sz[b];
ans+=(inord[a]+inord[b])*(sz[a]+sz[b]);
if (inord[a]<inord[b]){
swap(a,b);
if (DEBUG) cout<<"swap\n";
}
if (DEBUG) cout<<b<<"!\n";
//insert b into a
for (auto i:one[b]){
if (DEBUG) cout<<i.first<<"-->"<<b<<"\n";
if (find(i.first)==b||find(i.first)==a) continue;
if (one[a][i.first]){
ans-=(sz[a]+sz[b]);
inord[b]--;
frm[b][find(i.first)]--;
}else{
one[a][i.first]=1;
}
}
for (auto i:frm[b]){
frm[a][i.first]+=i.second;
}
if (DEBUG) cout<<"par["<<b<<"]="<<a<<"\n";
sz[a]+=sz[b];
par[b]=a;
}else{
ans+=sz[find(b)];
one[find(b)][a]=1;
frm[find(b)][find(a)]++;
inord[find(b)]++;
}
cout<<ans<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
