Submission #1265405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265405		rajarshi_basu	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	0 ms	320 KiB

joitter2

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

struct DSU {
    int n;
    vector<int> p;
    vector<int> sz;
    DSU(int n = 0): n(n), p(n+1), sz(n+1,1) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
    // merge b into a (caller ensures a != b and a is new root)
    void set_parent(int b, int a){
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;

    DSU dsu(N);

    // node-level outgoing edges for mutual detection
    vector<unordered_set<int>> g(N+1);
    for(int i=1;i<=N;i++) g[i].reserve(1);

    // component-level adjacency sets (store roots)
    vector<unordered_set<int>> out(N+1), in(N+1);
    for(int i=1;i<=N;i++){
        out[i].reserve(1);
        in[i].reserve(1);
    }

    // sizes available from dsu.sz
    // answer maintained as:
    // ans = sum over comps size[c]*(size[c]-1) + sum over directed comp edges a->b of size[a]*size[b]
    ll ans = 0;

    auto safe_find = [&](int x){ return dsu.find(x); };

    // helper to add an inter-component directed edge ra -> rb (roots)
    auto add_comp_edge = [&](int ra, int rb){
        if(ra == rb) return;
        // insert if not exists
        if(out[ra].insert(rb).second){
            in[rb].insert(ra);
            ans += 1LL * dsu.sz[ra] * dsu.sz[rb];
        }
    };

    // unite components a and b (by node indices). We'll merge smaller into larger.
    function<void(int,int)> unite = [&](int u, int v){
        int a = dsu.find(u), b = dsu.find(v);
        if(a == b) return;
        // ensure a is larger
        if(dsu.sz[a] < dsu.sz[b]) swap(a,b);

        // subtract old internal contributions
        ans -= 1LL * dsu.sz[a] * (dsu.sz[a] - 1);
        ans -= 1LL * dsu.sz[b] * (dsu.sz[b] - 1);

        // move out-edges of b
        // iterate over a snapshot to allow safe modification
        vector<int> tmp_out;
        tmp_out.reserve(out[b].size());
        for(int t : out[b]) tmp_out.push_back(t);
        for(int t0 : tmp_out){
            int t = dsu.find(t0);
            // remove b from in[t]
            auto it_in = in[t].find(b);
            if(it_in != in[t].end()) in[t].erase(it_in);

            if(t == a){
                // previously contributed sz[b]*sz[a], now internal -> remove that contribution
                ans -= 1LL * dsu.sz[b] * dsu.sz[a];
                // do not add any out-edge
            } else {
                // if a already has edge to t -> no net change in cross-sum
                if(out[a].find(t) == out[a].end()){
                    // create new edge a->t
                    out[a].insert(t);
                    in[t].insert(a);
                    // previously contribution was sz[b]*sz[t]; now it's (sz[a]+sz[b])*sz[t]
                    // increase by sz[a]*sz[t]
                    ans += 1LL * dsu.sz[a] * dsu.sz[t];
                } else {
                    // a already had edge to t; previous contributions (sz[a]*sz[t] + sz[b]*sz[t]) remain equal to (sz[a]+sz[b])*sz[t]
                    // no change needed
                }
            }
            // erase entry from out[b] (we will clear afterwards)
        }
        out[b].clear();

        // move in-edges of b
        vector<int> tmp_in;
        tmp_in.reserve(in[b].size());
        for(int s : in[b]) tmp_in.push_back(s);
        for(int s0 : tmp_in){
            int s = dsu.find(s0);
            // remove b from out[s]
            auto it_outs = out[s].find(b);
            if(it_outs != out[s].end()) out[s].erase(it_outs);

            if(s == a){
                // previously contributed sz[a]*sz[b], now internal -> remove that contribution
                ans -= 1LL * dsu.sz[a] * dsu.sz[b];
            } else {
                // if s already has edge to a -> no net change
                if(out[s].find(a) == out[s].end()){
                    out[s].insert(a);
                    in[a].insert(s);
                    // previously contribution sz[s]*sz[b], now becomes sz[s]* (sz[a]+sz[b]) so increase by sz[s]*sz[a]
                    ans += 1LL * dsu.sz[s] * dsu.sz[a];
                } else {
                    // already had edge s->a, no change
                }
            }
            // erase entry from in[b] (we will clear afterwards)
        }
        in[b].clear();

        // set parent and update size
        dsu.set_parent(b, a);

        // add new internal contribution
        ans += 1LL * dsu.sz[a] * (dsu.sz[a] - 1);
    };

    for(int i=0;i<M;i++){
        int A,B; cin >> A >> B;
        // add node-level edge A -> B
        g[A].insert(B);

        int ra = safe_find(A), rb = safe_find(B);

        // add component-level directed edge if inter-component
        if(ra != rb){
            add_comp_edge(ra, rb);
        }
        // if mutual, unite components of A and B
        if(g[B].find(A) != g[B].end()){
            unite(A, B);
        }

        cout << ans << '\n';
    }
    return 0;
}

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