#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,m,ans;
ll comp[100005];
vector<ll> dsu[100005];
set<ll> par[100005];
set<pll> edgenod[100005];
set<ll> edgecomp[100005];
bool fst=1;
void dsu_merge(ll c1,ll c2)
{
ll nr1=(int)dsu[c1].size()+(int)par[c1].size()+(int)edgenod[c1].size();
ll nr2=(int)dsu[c2].size()+(int)par[c2].size()+(int)edgenod[c2].size();
if(nr1<nr2)
swap(c1,c2);
ll sz2=dsu[c2].size();
ll sz1=dsu[c1].size();
ll val=(ll)dsu[c1].size()*(ll)dsu[c2].size();
val=val*2LL;
ans+=val;
val=(ll)par[c1].size()*sz2;
ans+=val;
set<ll> why;
for(ll x:par[c2])
{
edgenod[comp[x]].erase({x,c2});
if(edgecomp[comp[x]].find(c2)!=edgecomp[comp[x]].end())
edgecomp[comp[x]].erase(c2);
if(comp[x]==c1)
{
ans-=sz2;
continue;
}
if(par[c1].find(x)==par[c1].end())
{
why.insert(comp[x]);
par[c1].insert(x);
ans+=sz1;
edgenod[comp[x]].insert({x,c1});
edgecomp[comp[x]].insert(c1);
}
else
ans-=sz2;
}
for(pll p:edgenod[c2])
{
ll x=p.first;
ll c=p.second;
if(par[c].find(x)!=par[c].end())
par[c].erase(x);
if(c==c1)
{
ans-=(sz1+sz2);
continue;
}
why.insert(comp[x]);
edgenod[c1].insert({x,c});
edgecomp[c1].insert(c);
par[c].insert(x);
}
edgenod[c2].clear();
par[c2].clear();
edgecomp[c2].clear();
for(ll i:dsu[c2])
{
dsu[c1].push_back(i);
comp[i]=c1;
}
dsu[c2].clear();
if(par[c1].empty())
return;
vector<pll> pls;
bool found=0;
if(fst==1)
{
for(ll i:why)
if(edgecomp[comp[c1]].find(comp[i])!=edgecomp[comp[c1]].end())
if(edgecomp[comp[i]].find(comp[c1])!=edgecomp[comp[i]].end())
found=1;
}
for(ll i:par[c1])
if(edgecomp[comp[c1]].find(comp[i])!=edgecomp[comp[c1]].end())
if(edgecomp[comp[i]].find(comp[c1])!=edgecomp[comp[i]].end())
{
if(fst==1)
assert(found);
//dsu_merge(comp[i],comp[c1]);
pls.push_back({comp[i],comp[c1]});
}
fst=0;
for(pll p:pls)
{
ll a=p.first,b=p.second;
if(comp[a]!=comp[b])
dsu_merge(comp[a],comp[b]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
comp[i]=i;
dsu[i].push_back(i);
}
while(m--)
{
ll a,b;
cin>>a>>b;
ll c1=comp[a];
ll c2=comp[b];
if(c1==c2)
{
cout<<ans<<'\n';
continue;
}
if(edgecomp[c2].find(c1)!=edgecomp[c2].end())
{
fst=1;
dsu_merge(c1,c2);
cout<<ans<<'\n';
continue;
}
if(edgenod[c1].find({a,c2})==edgenod[c1].end())
{
ans+=dsu[c2].size();
edgenod[c1].insert({a,c2});
edgecomp[c1].insert(c2);
par[c2].insert(a);
}
cout<<ans<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
34140 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
34140 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
34140 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
