Submission #1271371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271371		LeonidCuk	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	822 ms	65296 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
long long int res=0;
vector<int>dsu,sz;
vector<set<int>>v,g,g1;
queue<pair<int,int>>q;
int vfind(int a)
{
    if(dsu[a]==a)return a;
    return dsu[a]=vfind(dsu[a]);
}
void dodadi(int a,int b)
{
    if(a==b)return;
    g[a].insert(b);
    g1[b].insert(a);
    if(g[b].count(a))q.push({a,b});
}
int golemina(int a)
{
    return g[a].size()+v[a].size()+g1[a].size();
}
void unija(int a,int b)
{
    if(a==b)return;
    if(golemina(b)>golemina(a))swap(a,b);
    res+=sz[a]*v[b].size()+sz[b]*v[a].size();
    dsu[b]=a;
    sz[a]+=sz[b];
    for(int i:v[b])
    {
        if(v[a].count(i))res-=sz[a];
        else v[a].insert(i);
    }
    g[a].erase(b);
    g1[a].erase(b);
    g[b].erase(a);
    g1[b].erase(a);
    for(int i:g[b])
    {
        g1[i].erase(b);
        dodadi(a,i);
    }
    for(int i:g1[b])
    {
        g[i].erase(b);
        dodadi(i,a);
    }
}
int main()
{
    int n,m,a,b;
    cin>>n>>m;
    v.resize(n+1);
    g.resize(n+1);
    g1.resize(n+1);
    dsu.resize(n+1);
    sz.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        dsu[i]=i;
        sz[i]=1;
        v[i].insert(i);
    }
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        b=vfind(b);
        if(vfind(a)!=b&&!v[b].count(a))
        {
            v[b].insert(a);
            a=vfind(a);
            res+=sz[b];
            dodadi(a,b);
            while(!q.empty())
            {
                auto p=q.front();
                q.pop();
                unija(vfind(p.first),vfind(p.second));
            }
       }
       cout<<res<<"\n";
    }
}

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