Submission #1265403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265403		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;

struct DSU {
    int n;
    vector<int> p, 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]); }
    // caller decides which root becomes parent
    void link_root(int child, int parent){
        p[child]=parent;
        sz[parent]+=sz[child];
    }
};

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

    DSU dsu(N);

    // out[u] = users v that u follows (to detect mutual quickly)
    vector<unordered_set<int>> out(N+1);
    out.shrink_to_fit();

    // For each component root r:
    // sources[r] = set of distinct users x that have at least one edge x->(any member of r)
    // inside[r]  = count of x in sources[r] that are also members of r
    vector<unordered_set<int>> sources(N+1);
    vector<long long> inside(N+1, 0);

    long long ans = 0;

    auto add_source = [&](int comp, int x){
        // Insert x into sources[comp]; update ans and inside if first time
        if(sources[comp].insert(x).second){
            ans += dsu.sz[comp];
            if(dsu.find(x)==comp){
                inside[comp] += 1;
                ans -= 1; // exclude self-follow
            }
        }
    };

    auto unite = [&](int a, int b){
        int ra = dsu.find(a), rb = dsu.find(b);
        if(ra==rb) return;

        // Parent by component size
        if(dsu.sz[ra] < dsu.sz[rb]) swap(ra, rb); // ra will be parent root

        // Ensure we merge smaller sources-set into larger (small-to-large)
        if(sources[ra].size() < sources[rb].size()){
            swap(sources[ra], sources[rb]);
            swap(inside[ra], inside[rb]);
        }

        // Remove old contributions
        long long term_ra = 1LL * dsu.sz[ra] * (long long)sources[ra].size() - inside[ra];
        long long term_rb = 1LL * dsu.sz[rb] * (long long)sources[rb].size() - inside[rb];
        ans -= term_ra + term_rb;

        // Prepare new values
        long long extra_inside = 0;
        size_t before_sz = sources[ra].size();

        // Merge sources[rb] into sources[ra]
        for(const int s : sources[rb]){
            auto ins = sources[ra].insert(s);
            if(ins.second){
                int rs = dsu.find(s); // membership BEFORE union
                if(rs==ra || rs==rb) extra_inside += 1;
            }
        }
        sources[rb].clear();

        inside[ra] = inside[ra] + inside[rb] + extra_inside;
        long long new_comp_size = dsu.sz[ra] + dsu.sz[rb];
        long long new_sources_cnt = (long long)sources[ra].size();

        // Add new contribution
        ans += new_comp_size * new_sources_cnt - inside[ra];

        // Union components in DSU
        dsu.link_root(rb, ra);
    };

    for(int i=1;i<=M;i++){
        int A,B; cin>>A>>B;

        // Add A->B if new (problem guarantees no duplicates, but keep safe)
        if(out[A].insert(B).second){
            int cb = dsu.find(B);
            add_source(cb, A);
        }

        // If mutual found, merge components of A and B
        if(out[B].count(A)) unite(A,B);

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

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