Submission #1162290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162290		spycoderyt	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	641 ms	103932 KiB

joitter2

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 3e5+5;
set<int> child[N];
int sz[N],p[N],ans=0;
set<int> graph[N],rgraph[N];
queue<pair<int,int> > to_merge;
void add_weak(int a,int b) {
    graph[a].insert(b);
    rgraph[b].insert(a);
    if(graph[b].count(a)) to_merge.push({a,b});
}
int fp(int u) {
    if(p[u] == u)return u;
    else return fp(p[u]);
}
int fsz(int u) {return graph[u].size() + rgraph[u].size() + child[u].size();}
void onion(int a,int b) {
    if(a==b)return;
    if(fsz(a) < fsz(b))swap(a,b);
    ans+=sz[a] * child[b].size() + sz[b] * child[a].size();
    p[b] = a;
    sz[a]+=sz[b];
    for(auto e : child[b]) {
        if(child[a].count(e))ans-=sz[a];
        else child[a].insert(e);
    }
    graph[a].erase(b);
    rgraph[a].erase(b);
    graph[b].erase(a);
    rgraph[b].erase(a);
    for(auto e : graph[b]) {
        rgraph[e].erase(b);
        add_weak(a,e);
    }
    for(auto e : rgraph[b]){
        graph[b].erase(e);
        add_weak(e,a);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int a,b,n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++) {
        p[i]=i;
        sz[i]=1;
        child[i].insert(i);
    }
    for(int i = 0;i<m;i++) {
        cin>>a>>b;
        b = fp(b);
        if(fp(a)!=b&&!child[b].count(a)){
            child[b].insert(a);
            ans+=sz[b];
            a=fp(a);
            add_weak(a,b);
            while(to_merge.size()) {
                auto [a,b] = to_merge.front();
                to_merge.pop();
                onion(fp(a),fp(b));
            }
        }
        cout<<ans<<"\n";
    }
}

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