Submission #1177021

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

joitter2

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';

const int N = 1e5;

struct DSU {
    int n;
    vector<int> par, size;
    vector<bitset<N> > msk;

    DSU() {
    }

    DSU(int n) : n(n) {
        par.assign(n, 0);
        size.assign(n, 1);
        msk.assign(n, 0);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            msk[i][i] = true;
        }
    }

    int find(int v) {
        return (v == par[v] ? v : par[v] = find(par[v]));
    }

    void set(int u, int v) {
        msk[find(v)][u] = true;
    }

    bool get(int u, int v) {
        return msk[find(v)][u];
    }

    ll get_ans(int u) {
        u = find(u);
        ll m = size[u];
        return m * (msk[u].count() - 1);
    }

    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        par[b] = a;
        size[a] += size[b];
        msk[a] |= msk[b];
        return true;
    }

    int sz(int v) {
        return size[find(v)];
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    set<pair<int, int> > edges;
    DSU dsu(n);
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        if (edges.contains({v, u})) {
            ans -= dsu.get_ans(u);
            ans -= dsu.get_ans(v);
            dsu.unite(u, v);
            ans += dsu.get_ans(u);
        } else if (!dsu.get(u, v)) {
            dsu.set(u, v);
            ans += dsu.sz(v);
        }
        edges.insert({u, v});
        cout << ans << nl;
    }
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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