Submission #1284128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284128		polarity	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	1026 ms	94608 KiB

joitter2

/**
 * Solution by Charles Ran (polarity.sh)
 * Date: 2025-10-26
 * Contest: JOI 2020
 * Problem: joitter2
**/

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

/** 
 * DS: Disjoint Set Union 
 * PURPOSE: Dynamically updates connectedness of graph by adding edges
 * TIME: amortized O(a(N)) to query
*/
class DSU {
    private: 
        vector<int> parents;
        vector<ll> sizes;
        vector<map<int, ll>> from;
        vector<set<int>> fromEl;
        vector<set<pii>> to;
        vector<set<int>> els;
        ll ans = 0;
    
    public:
        DSU(int size) : parents(size), sizes(size, 1), from(size), fromEl(size), to(size), els(size){
            for (int i = 0; i < size; i++){
                parents[i] = i;
                els[i].insert(i);
            }
        }

        int find(int x){
            return (parents[x] == x ? x : (parents[x] = find(parents[x])));
        }

        ll completeCount(ll x){
            return sizes[x] * (sizes[x] - 1);
        }

        void merge(int a, int b){
            int parentA = find(a);
            int parentB = find(b);
            if (parentA == parentB){
                return;
            }

            // merge these
            ans -= from[parentA][parentB] * sizes[parentA];
            ans -= from[parentB][parentA] * sizes[parentB];
            ans -= completeCount(parentA);
            ans -= completeCount(parentB);

            if (sizes[parentA] > sizes[parentB]){
                swap(parentA, parentB);
            }
            
            for (int x : els[parentA]){
                if (fromEl[parentB].contains(x)){
                    fromEl[parentB].erase(x);
                    to[parentA].erase({x, parentB});
                }

                els[parentB].insert(x);
            }

            ans += sizes[parentA] * (ll)sz(fromEl[parentB]);

            vi merges;

            for (int x : fromEl[parentA]){
                int parentX = find(x);
                to[parentX].erase({x, parentA});
                if (parentX == parentB) continue;

                if (fromEl[parentB].contains(x)){
                    ans -= sizes[parentA];
                    continue;
                }

                if (from[parentX][parentB] > 0){
                    merges.pb(parentX);
                }

                to[parentX].insert({x, parentB});
                from[parentB][parentX]++;
                fromEl[parentB].insert(x);
                ans += sizes[parentB];
            }

            fromEl[parentA] = {};

            for (auto& [el, comp] : to[parentA]){
                if (from[parentB][comp] > 0){
                    merges.pb(comp);
                }

                from[comp][parentB]++;
                from[comp].erase(parentA);
                to[parentB].insert({el, comp});
            }

            to[parentA] = {};

            sizes[parentB] += sizes[parentA];
            parents[parentA] = parentB;

            ans += completeCount(parentB);      

            for (int comp : merges){
                merge(parentB, comp);
            }
        }

        bool unite(int a, int b){
            int parentA = find(a);
            int parentB = find(b);
            if (parentA == parentB){
                return false;
            }

            if (from[parentA][parentB] == 0){
                if (!fromEl[parentB].contains(a)){
                    from[parentB][parentA]++;
                    ans += sizes[parentB];
                }
                to[parentA].insert({a, parentB});
                fromEl[parentB].insert(a);

                return false;
            }

            merge(parentA, parentB);
            return true;
        }

        bool connected(int a, int b){
            return find(a) == find(b);
        }

        ll answer(){
            return ans;
        }
};

void solve(){
    int n, m; cin >> n >> m;
    
    DSU dsu(n);
    rep(i, 0, m){
        int a, b; cin >> a >> b;
        --a; --b;

        dsu.unite(a, b);

        cout << dsu.answer() << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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