#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<21);
const ll C=20;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,m,x[N],y[N],sz[N],dir[N],ans;
vector<ll> que[N],rem[N];
map<pll,bool> vis;
set<ll> in[N];
ll f(ll id){return (id==dir[id]?id:dir[id]=f(dir[id]));}
void merge(ll a,ll b){
a=f(a);b=f(b);
if(a==b)return;
if(SZ(in[a])>SZ(in[b]))swap(a,b);
ans-=(SZ(in[b])+sz[b]-1)*sz[b]+(SZ(in[a])+sz[a]-1)*sz[a];
sz[b]+=sz[a];sz[a]=0;dir[a]=b;
while(SZ(in[a])){
ll tmp=*in[a].begin();
in[a].erase(in[a].begin());
in[b].insert(tmp);
}
ans+=(SZ(in[b])+sz[b]-1)*sz[b];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP(i,m)cin>>x[i]>>y[i];
REP(i,m)que[(1<<(C-1))].pb(i);
for(int i=C-1;i>=0;i--){
vis.clear();
REP1(j,n)dir[j]=j;
for(ll j=0;j<(1<<C);j++){
if(x[j]!=0&&y[j]!=0){
vis[mp(x[j],y[j])]=1;
if(vis[mp(y[j],x[j])]==1)dir[f(x[j])]=f(y[j]);
}
if((j&(1<<i))&&(j&((1<<i)-1))==0){
for(auto k:que[j]){
if(i==0){
if(f(x[k])==f(y[k]))rem[j].pb(k);
else rem[j+1].pb(k);
}else{
if(f(x[k])==f(y[k]))que[j-(1<<(i-1))].pb(k);
else que[j+(1<<(i-1))].pb(k);
}
}
}
}
}
vis.clear();
REP1(i,n)dir[i]=i,sz[i]=1;
REP(i,m){
vis[mp(x[i],y[i])]=1;
for(ll j:rem[i]){
if(j>=i)continue;
ans-=sz[f(y[j])];
in[f(y[j])].erase(x[j]);
}
if(vis[mp(y[i],x[i])]==1){
merge(x[i],y[i]);
}else{
if(in[f(y[i])].find(x[i])==in[f(y[i])].end()&&f(x[i])!=f(y[i])){
ans+=sz[f(y[i])];
in[f(y[i])].insert(x[i]);
}
}
cout<<ans<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
197368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
197368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
197368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
