Submission #1257009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257009		nguyn	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	847 ms	64940 KiB

joitter2

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 1e5 + 5;

int n, m;
int lab[N];
ll res = 0;
set<int> comp[N];
set<int> g[N], rev_g[N];
vector<pii> edges;

int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void add(int u, int v) {
    g[u].insert(v);
    rev_g[v].insert(u);
    if (g[v].count(u)) {
        edges.pb({u, v});
    }
}

void join(int u, int v) {
    if ((u = find(u)) == (v = find(v))) return;
    if (comp[u].size() + g[u].size() + rev_g[u].size() < comp[v].size() + g[v].size() + rev_g[v].size()) swap(u, v);
    res += 1ll * - lab[u] * comp[v].size();
    res += 1ll * - lab[v] * comp[u].size();
    for (int x : comp[v]) {
        if (comp[u].count(x)) {
            res += lab[u] + lab[v];
        }
        else {
            comp[u].insert(x);
        }
    }
    g[u].erase(v);
    g[v].erase(u);
    rev_g[u].erase(v);
    rev_g[v].erase(u);
    for (int x : g[v]) {
        rev_g[x].erase(v);
        add(u, x);
    }
    for (int x : rev_g[v]) {
        g[x].erase(v);
        add(x, u);
    }
    lab[u] += lab[v];
    lab[v] = u;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        lab[i] = -1;
        comp[i].insert(i);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int x = find(u);
        int y = find(v);
        if (x != y && !comp[y].count(u)) {
            comp[y].insert(u);
            res -= lab[y];
            add(x, y);
            while(!edges.empty()) {
                int a, b;
                tie(a, b) = edges.back();
                edges.pop_back();
                join(a, b);
            }
        }
        cout << res << '\n';
    }
}

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