Submission #1249291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249291		ender_shayan	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	8 ms	16704 KiB

joitter2

#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;
        in[uu][v]+=t;
        if(in[v][uu] && t)
            vec.pb(uu);
    }
    for(pii p:in[u]){
        int uu=p.F,t=p.S;
        in[v][uu]+=t;
        out[uu][v]+=t;
        if(out[v][uu] && t)
            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);
        }
    }

}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83