Submission #1227978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227978		pfang	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	71 ms	141384 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 1000005;

int ans = 0;
int par[MAXN], sizes[MAXN];
set<int> from[MAXN], to[MAXN], outerBozos[MAXN];
// from [x] => x -> y, from[x] = y
// outers not in dsu group

queue<pair<int, int>> unites;

void removeThem(int a, int b){
    to[a].erase(b);
    to[b].erase(a);
    from[a].erase(b);
    from[b].erase(a);
}

int find(int cur){
    if(cur != par[cur]){
        par[cur] = find(par[cur]);
    }
    return par[cur];
}

void unite(int a, int b){
    int pA = find(a);
    int pB = find(b);
    
    if(outerBozos[pA].size() + to[pA].size() + from[pA].size() < outerBozos[pB].size() + to[pB].size() + from[pB].size()){
        swap(pA, pB);
    }
    // add to the answer depending on how the new connection brings the 
    // outers in and internal connects, but we overcount and we have to erase some if 
    // they already existed
    ans += sizes[pA] * outerBozos[pB].size() + sizes[pB] * outerBozos[pA].size();
    par[pB] = pA;
    sizes[pA] += sizes[pB];
    // removal
    for(auto i : outerBozos[pB]){
        if(outerBozos[pA].count(i) != 0){
             // bad, already has a connection, overcounted
            ans -= sizes[pA];
        }else{
            // add it in
            outerBozos[pA].insert(i);
        }
    }
    
    // break the ties that the nodes has?
    //yeah
    removeThem(pA, pB);
    
    //connect the previous elements relating to b to a ( pB -> x)
    for(auto i : to[pB]){
        from[i].erase(pB); // sever connection, readd to a
        if(to[pA].count(i) != 0){
            continue;
        }
    	to[pA].insert(i);
    	from[i].insert(pA);
    	if(to[i].count(pA) != 0){ // i -> pA exists
    	    unites.push({pA, i});
    	}
    }
    
    for(auto i : from[pB]){
        // now sever reverse connection
        to[i].erase(pB);
        if(to[i].count(pA) != 0){
            continue;
        }
        to[i].insert(pA);
        from[pA].insert(i);
        if(to[pA].count(i) != 0){
            unites.push({i, pA});
        }
    }
    to[pB].clear();
    from[pB].clear();
    outerBozos[pB].clear();
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
		par[i] = i;
		sizes[i] = 1;
		outerBozos[i].insert(i);
	}
	
    while(m--){
        int a, b;
        cin >> a >> b;
        int pA = find(a);
        int pB = find(b);
        if(pA != pB && outerBozos[pB].count(a) == 0){
            ans += sizes[pB];
            outerBozos[pB].insert(a);
                to[pA].insert(pB);
                from[pB].insert(pA);
                if(to[pB].count(pA) != 0){
                    unites.push({pA, pB});
                }
            
            
            while(!unites.empty()){
                auto i = unites.front();
                unites.pop();
                unite(i.first, i.second);
            }
        }
        cout << ans << '\n';
    }
}

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