Submission #1117225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117225		vjudge1	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	734 ms	69628 KiB

joitter2

#include<bits/stdc++.h>
#define int long long
using namespace std;
int par[100100],sz[100100],ans;
set<int>adj[100100],radj[100100],st[100100];
queue<pair<int,int>> ops;
int abp(int a){
    return par[a]?par[a]=abp(par[a]):a;
}
void weak(int a,int b){
    adj[a].insert(b);
    radj[b].insert(a);
    if(adj[b].count(a))
        ops.push({a,b});
}
inline int ssz(int x){
    return st[x].size()+radj[x].size()+adj[x].size();
}
void merge(int a,int b){
    if(a==b)return;
    ans+=sz[a]*st[b].size()+sz[b]*st[a].size();
    if(ssz(a)<ssz(b))swap(a,b);
    par[b]=a;sz[a]+=sz[b];
    for(auto i:st[b])
        if(st[a].count(i))
            ans-=sz[a];
        else st[a].insert(i);
    adj[a].erase(b);
    adj[b].erase(a);
    radj[a].erase(b);
    radj[b].erase(a);
    for(auto i:adj[b])
        radj[i].erase(b),
        weak(a,i);
    for(auto i:radj[b])
        adj[i].erase(b),
        weak(i,a);
}
void dostuf(int a,int b){
    b=abp(b);
    if(abp(a)!=b&&!st[b].count(a)){
        st[b].insert(a);
        ans+=sz[b];
        a=abp(a);
        weak(a,b);
        while(ops.size()){
            auto[a,b]=ops.front();
            ops.pop();
            merge(abp(a),abp(b));
        }
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        st[i].insert(i),sz[i]=1;
    while(m--){
        int a,b;
        cin>>a>>b;
        dostuf(a,b);
        cout<<ans<<'\n';
    }
}

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