| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249290 | ender_shayan | Making Friends on Joitter is Fun (JOI20_joitter2) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define pb push_back
#define Mp make_pair
#define for1(n) for(int i=1;i<=n;i++)
#define for0(n) for(int i=0;i<n;i++)
#define set_dec(x) cout << fixed << setprecision(x);
#define endl '\n'
const ll mod=1e9+7;
const int N=1e5+10,L=21,base=701;
int A[N],B[N],C[N],D[N],n,m,k,q,dp[N],par[N],sz[N],degin[N];
vector<int>g[N];
map<int,int>in[N],out[N],is[N];
ll ans;
int get_par(int v){
if(par[v]==0)return v;
return par[v]=get_par(par[v]);
}
void merg(int u,int v){
u=get_par(u);
v=get_par(v);
if(u==v)return;
if(sz[u]+in[u].size()+out[u].size()+is[u].size()>sz[v]+in[v].size()+out[v].size()+is[v].size())swap(u,v);
par[u]=v;
ans+=1ll*sz[v]*sz[u]*2;
ans+=degin[v]*sz[u]+degin[u]*sz[v];
degin[v]+=degin[u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
vector<int>vec;
for(pii p:out[u]){
int uu=p.F,t=p.S;
out[v][uu]+=t;
if(in[v][uu])
vec.pb(uu);
}
for(pii p:in[u]){
int uu=p.F,t=p.S;
in[uu][v]+=t;
if(out[v][uu])
vec.pb(uu);
}
for(int u:vec){
ans-=out[v][u]*sz[u]+out[u][v]*sz[v];
degin[v]-=out[u][v];
degin[u]-=out[v][u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
}
sz[v]+=sz[u];
for(pii p:is[u])is[v][p.F]++;
out[u].clear();in[u].clear();is[u].clear();
for(int u:vec)merg(u,v);
}
int main(){
fast_io
cin>>n>>m;
for1(n)sz[i]=1;
for(int _=0;_<m;_++,cout<<ans<<endl){
int u,v;cin>>u>>v;
int uu=u;
u=get_par(u);v=get_par(v);
if(u==v)continue;
if(is[v][uu])continue;
is[v][uu]=1;
ans+=sz[v];
out[u][v]++;
in[v][u]++;degin[v]++;
if(in[u][v]){
ans-=1ll*out[u][v]*sz[v]+1ll*out[v][u]*sz[u];
degin[v]-=out[u][v];
degin[u]-=out[v][u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
merg(u,v);
}
}
}#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define pb push_back
#define Mp make_pair
#define for1(n) for(int i=1;i<=n;i++)
#define for0(n) for(int i=0;i<n;i++)
#define set_dec(x) cout << fixed << setprecision(x);
#define endl '\n'
const ll mod=1e9+7;
const int N=1e5+10,L=21,base=701;
int A[N],B[N],C[N],D[N],n,m,k,q,dp[N],par[N],sz[N],degin[N];
vector<int>g[N];
map<int,int>in[N],out[N],is[N];
ll ans;
int get_par(int v){
if(par[v]==0)return v;
return par[v]=get_par(par[v]);
}
void merg(int u,int v){
u=get_par(u);
v=get_par(v);
if(u==v)return;
if(sz[u]+in[u].size()+out[u].size()+is[u].size()>sz[v]+in[v].size()+out[v].size()+is[v].size())swap(u,v);
par[u]=v;
ans+=1ll*sz[v]*sz[u]*2;
ans+=degin[v]*sz[u]+degin[u]*sz[v];
degin[v]+=degin[u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
vector<int>vec;
for(pii p:out[u]){
int uu=p.F,t=p.S;
out[v][uu]+=t;
if(in[v][uu])
vec.pb(uu);
}
for(pii p:in[u]){
int uu=p.F,t=p.S;
in[uu][v]+=t;
if(out[v][uu])
vec.pb(uu);
}
for(int u:vec){
ans-=out[v][u]*sz[u]+out[u][v]*sz[v];
degin[v]-=out[u][v];
degin[u]-=out[v][u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
}
sz[v]+=sz[u];
for(pii p:is[u])is[v][p.F]++;
out[u].clear();in[u].clear();is[u].clear();
for(int u:vec)merg(u,v);
}
int main(){
fast_io
cin>>n>>m;
for1(n)sz[i]=1;
for(int _=0;_<m;_++,cout<<ans<<endl){
int u,v;cin>>u>>v;
int uu=u;
u=get_par(u);v=get_par(v);
if(u==v)continue;
if(is[v][uu])continue;
is[v][uu]=1;
ans+=sz[v];
out[u][v]++;
in[v][u]++;degin[v]++;
if(in[u][v]){
ans-=1ll*out[u][v]*sz[v]+1ll*out[v][u]*sz[u];
degin[v]-=out[u][v];
degin[u]-=out[v][u];
out[v][u]=out[u][v]=in[v][u]=in[u][v]=0;
merg(u,v);
}
}
}