Submission #841246

#	Time	Username	Problem	Language	Result	Execution time	Memory
841246		Ahmed57	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1340 ms	69380 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
set<int> ch[100001],adj[100001],rev[100001];
long long ans = 0;
long long pr[100001],sz[100001];
queue<pair<int,int>> to;
void insertcon(int x,int y){
    adj[x].insert(y);
    rev[y].insert(x);
    if(adj[y].count(x))to.push({x,y});
}
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
int dsu_sz(int x){
    return ch[x].size()+adj[x].size()+rev[x].size();
}
void mergegroup(int a,int b){
    if(a==b)return ;
    if(dsu_sz(a)<dsu_sz(b))swap(a,b);
    ans+=sz[a]*ch[b].size()+sz[b]*ch[a].size();
    pr[b] = a;sz[a]+=sz[b];
    for(auto i:ch[b]){
        if(ch[a].count(i))ans-=sz[a];
        else ch[a].insert(i);
    }
    adj[a].erase(b);rev[b].erase(a);
    adj[b].erase(a);rev[a].erase(b);
    for(auto i:adj[b]){
        rev[i].erase(b);
        insertcon(a,i);
    }for(auto i:rev[b]){
        adj[i].erase(b);
        insertcon(i,a);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        pr[i] = i;
        sz[i] = 1;
        ch[i].insert(i);
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        b = find(b);
        if(find(a)!=b&&!ch[b].count(a)){
            ch[b].insert(a);
            ans+=sz[b];
            a = find(a);
            insertcon(a,b);
            while(!to.empty()){
                int A = to.front().first;
                int B = to.front().second;
                mergegroup(find(A),find(B));
                to.pop();
            }
        }
        cout<<ans<<endl;
    }
}

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