Submission #1123257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123257		I_FloPPed21	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	800 ms	65348 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,m;
set<int> graph[N],rgraph[N],child[N];
int comp[N];
int size_comp[N];
int find(int point)
{
    //cout<<point<<" "<<comp[point]<<'\n';
    if(comp[point]==point)
    {
        return point;
    }
    else
    {
        int t=find(comp[point]);
        comp[point]=t;
        return t;
    }
}
long long ans=0;
vector<pair<int,int>> to_merge;
void merge_weak(int a,int b)
{
    graph[a].insert(b);
    rgraph[b].insert(a);

    if(graph[b].count(a))
        to_merge.push_back({a,b});
}
int dsu_size(int a)
{
    return graph[a].size()+rgraph[a].size()+child[a].size();
}
void uneste(int a,int b)
{
    if(find(a)==find(b))
        return;
    if(dsu_size(a)<dsu_size(b))
        swap(a,b);
    ans+=size_comp[a]*child[b].size()+size_comp[b]*child[a].size();
    size_comp[a]+=size_comp[b];
    comp[b]=a;
    for(auto u:child[b])
        {
            if(child[a].count(u))
                ans-=size_comp[a];
            else
                child[a].insert(u);
        }

    graph[a].erase(b);
    rgraph[a].erase(b);
    graph[b].erase(a);
    rgraph[b].erase(a);
    for(auto u:graph[b])
    {
        rgraph[u].erase(b);
        merge_weak(a,u);
    }
    for(auto u:rgraph[b])
    {
        graph[u].erase(b);
        merge_weak(u,a);
    }
}
void citeste()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        size_comp[i]=1;

        comp[i]=i;
        child[i].insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        int top=find(b);
        if(find(a)!=find(b)&&child[top].find(a)==child[top].end())
        {
            child[top].insert(a);
            ans+=size_comp[top];
            int top2=find(a);
            merge_weak(top2,top);
            while(to_merge.empty()==false)
            {
                int x,y;
                tie(x,y)=to_merge.back();
                to_merge.pop_back();
                uneste(find(x),find(y));
            }
        }
        cout<<ans<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    return 0;
}

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