Submission #895319

#	Time	Username	Problem	Language	Result	Execution time	Memory
895319		box	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	865 ms	73220 KiB

joitter2

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int MAXN = 1e5;

int N, M;
int sz[MAXN], parent[MAXN];
list<int> vertices[MAXN];
set<int> out[MAXN], in[MAXN];
set<int> in_v[MAXN];
i64 num_edges;

int find(int i) {
    return parent[i] == i ? i : parent[i] = find(parent[i]);
}

void add_edge(int i, int j) {
    int x = find(i);
    int y = find(j);
    if (x == y) return;
    if (in_v[y].count(i)) return;
    in_v[y].insert(i);
    num_edges += sz[y];
    queue<pii> mrg;
    auto ins = [&](int x, int y) {
        out[x].insert(y);
        in[y].insert(x);
        if (out[y].count(x)) mrg.push({x, y});
    };
    ins(x, y);
    while (sz(mrg)) {
        auto [x, y] = mrg.front(); mrg.pop();
        x = find(x);
        y = find(y);
        if (x != y) {
            if (sz[x] < sz[y]) swap(x, y);
            num_edges += i64(sz(in_v[x])) * sz[y];
            num_edges += i64(sz(in_v[y])) * sz[x];
            out[x].erase(y);
            in[x].erase(y);
            for (int i : exchange(in_v[y], {})) {
                if (in_v[x].count(i)) num_edges -= sz[x] + sz[y];
                else in_v[x].insert(i);
            }
            for (int i : exchange(out[y], {})) {
                if (i == x) continue;
                in[i].erase(y);
                ins(x, i);
            }
            for (int i : exchange(in[y], {})) {
                if (i == x) continue;
                out[i].erase(y);
                ins(i, x);
            }
            vertices[x].splice(end(vertices[x]), vertices[y]);
            parent[y] = x;
            sz[x] += sz[y];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        sz[i] = 1;
        parent[i] = i;
        vertices[i] = {i};
        in_v[i] = {i};
    }
    while (M--) {
        int i, j;
        cin >> i >> j, i--, j--;
        add_edge(i, j);
        cout << num_edges << '\n';
    }
}

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