Submission #1226355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226355		rwang	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	4 ms	9792 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5;

int p[N];
ll sz[N];
set<int> cmp[N];
set<int> fol[N];//nodes in each component, followers of anyone in cmp
queue<pair<int, int>> q;

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

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
        return;
    }
    if (sz[x] < sz[y]) {
        swap(x, y);
    }
    for (int c : cmp[y]) {
        cmp[x].insert(c);
    }
    for (int f : fol[y]) {
        f = find(f);
        if (cmp[x].count(f) == 0) {
            fol[x].insert(f);
            if (fol[f].count(x)) {
                q.push({x, f});
            }
        }
    }
    // fol[y].clear();
    sz[x] += sz[y];
    p[y] = x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        cmp[i].insert(i);
    }
    ll ans = 0;
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        a = find(a);
        b = find(b);
        if (fol[b].count(a) == 0) {
            ans += sz[b];
        }
        fol[b].insert(a);
        if (fol[a].count(b)) {
            q.push({a, b});
        }
        while (!q.empty()) {
            int a = q.front().first, b = q.front().second;
            q.pop();
            ans -= sz[a] * (sz[a] - 1);
            ans -= fol[a].size() * sz[a];
            ans -= sz[b] * (sz[b] - 1);
            ans -= fol[b].size() * sz[b];
            fol[a].erase(b);
            fol[b].erase(a);
            merge(a, b);
            a = find(a);
            ans += sz[a] * (sz[a] - 1);
            ans += fol[a].size() * sz[a];
        }
        cout << ans << "\n";
    }
}

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