Submission #953232

#	Time	Username	Problem	Language	Result	Execution time	Memory
953232		andrei_boaca	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	17 / 100	4563 ms	140228 KiB

joitter2

#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];
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;
    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())
        {
            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;
        }
        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<ll> v;
    for(ll i:par[c1])
    {
        v.push_back(comp[i]);
        if(v.size()>500)
            break;
    }
    for(auto it=prev(par[c1].end());v.size()<1000;it--)
    {
        v.push_back((*it));
        if(it==par[c1].begin())
            break;
    }
    for(ll i:v)
        if(edgecomp[c1].find(i)!=edgecomp[c1].end())
            if(edgecomp[i].find(c1)!=edgecomp[i].end())
            {
                dsu_merge(i,c1);
                break;
            }
}
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())
        {
            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;
}

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