Submission #946371

#	Time	Username	Problem	Language	Result	Execution time	Memory
946371		Pannda	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	0 ms	348 KiB

joitter2

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

struct DSU {
    int n;
    vector<int> f, siz;

    DSU(int n) : n(n), f(n), siz(n, 1) { iota(f.begin(), f.end(), 0); };

    int leader(int u) {
        while (u != f[u]) {
            u = f[u] = f[f[u]];
        }
        return u;
    }

    bool unionize(int u, int v) {
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        siz[v] += siz[u];
        f[u] = v;
        return true;
    }

    int size(int u) {
        return siz[leader(u)];
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    long long res = 0;
    DSU dsu(n);

    vector<map<int, int>> out(n);
    vector<map<int, int>> in(n);
    vector<int> cnt_out(n, 0);
    vector<int> cnt_in(n, 0);

    auto addEdge = [&](auto self, int u, int v, int c) -> void {
        if (dsu.same(u, v) || out[u].count(v)) return;

        if (!out[v].count(u)) { // no v -> u, no need for merging
            out[u][v] += c;
            in[v][u] += c;
            cnt_out[u] += c;
            cnt_in[v] += c;
            res += 1LL * c * dsu.size(v);
            return;
        }

        // removes v -> u
        res -= 1LL * dsu.size(u) * out[v][u];
        cnt_out[v] -= out[v][u];
        cnt_in[v] -= in[v][u];
        cnt_out[u] -= out[u][v];
        cnt_in[u] -= in[u][v];
        out[v].erase(u);
        in[u].erase(v); // this probably is the only place where something on u is erased

        if (out[u].size() + in[u].size() > out[v].size() + in[v].size()) swap(u, v);

        res += 2LL * dsu.size(u) * dsu.size(v);
        res += 1LL * cnt_in[v] * dsu.size(u);

        for (auto [w, c] : out[u]) { // removes u -> w
            res -= 1LL * c * dsu.size(w);
            cnt_in[w] -= in[w][u];
            in[w].erase(u);
        }
        for (auto [w, c] : in[u]) { // removes w -> u
            res -= 1LL * c * dsu.size(u);
            cnt_out[w] -= out[w][u];
            out[w].erase(u);
        }
        dsu.unionize(u, v);
        // here u shouldn't be seen by any other node

        for (auto [w, c] : out[u]) { // adds v -> w
            self(self, v, w, c);
        }
        for (auto [w, c] : in[u]) { // adds w -> v
            self(self, w, v, c);
        }
    };

    while (m--) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        u = dsu.leader(u);
        v = dsu.leader(v);
        addEdge(addEdge, u, v, 1);
        cout << res << '\n';
    }
}

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