Submission #1226481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226481		rwang	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	528 ms	67088 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5;

int p[N];
ll sz[N], ans;
set<int> c[N], adj[N], radj[N];
queue<pair<int, int>> q;

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

void addEdge(int i, int j) {
    if (adj[i].count(j)) return;
    adj[i].insert(j);
    radj[j].insert(i);
    if (adj[j].count(i)) {
        q.push({i, j});
    }
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    ans += sz[x] * c[y].size() + sz[y] * c[x].size();
    adj[x].erase(y);
    adj[y].erase(x);
    radj[x].erase(y);
    radj[y].erase(x);
    sz[x] += sz[y];
    p[y] = x;
    for (int i : adj[y]) {
        radj[i].erase(y);
        addEdge(x, i);
    }
    for (int i : radj[y]) {
        adj[i].erase(y);
        addEdge(i, x);
    }
    for (int i : c[y]) {
        if (c[x].count(i)) ans -= sz[x];
        else c[x].insert(i);
    }
}

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;
        c[i].insert(i);
    }
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        b = find(b);
        if (find(a) != b && c[b].count(a) == 0) {
            c[b].insert(a);
            ans += sz[b];
            a = find(a);
            addEdge(a, b);
            while (!q.empty()) {
                auto cur = q.front();
                q.pop();
                merge(cur.first, cur.second);
            }
        }
        cout << ans << "\n";
    }
}

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