제출 #956755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956755		Sharky	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	3 ms	16988 KiB

joitter2

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

#define int long long
#define siz(x) (int)x.size()
const int N = 100005;

int p[N], sz[N], ans = 0;
map<pair<int, int>, int> mp;
vector<int> vt[N];
set<int> st[N], g1[N], g2[N];

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

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (siz(g1[u]) + siz(g2[u]) < siz(g1[v]) + siz(g2[v])) swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    for (int i : g1[v]) {
        g2[i].erase(v);
        if (find(i) != find(u)) {
            g2[i].insert(u);
            g1[u].insert(i);
            mp[{u, i}] += mp[{v, i}];
        }
        mp[{v, i}] = 0;
    }
    g1[v].clear();
    for (int i : g2[v]) {
        g1[i].erase(v);
        if (find(i) != find(u)) {
            g1[i].insert(u);
            g2[u].insert(i);
            mp[{i, u}] += mp[{i, v}];
        }
        mp[{i, v}] = 0;
    }
    g2[v].clear();
    for (int i : st[v]) if (find(u) != find(i)) st[u].insert(i);
    st[v].clear();
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (st[find(v)].count(u)) { // need to delete?
            cout << ans << '\n';
            continue;
        }
        if (find(u) != find(v)) st[find(v)].insert(u);
        u = find(u), v = find(v);
        if (u == v) {
            cout << ans << '\n';
            continue;
        }
        mp[{u, v}]++;
        g1[u].insert(v);
        g2[v].insert(u);
        ans += sz[v];
        if (g1[v].count(u)) {
            ans += sz[u] * sz[v] * 2;
            // cout << ans << '\n';
            // ans += (siz(st[u]) - mp[{v, u}]) * sz[v];
            ans += (siz(g2[u]) - (mp[{v, u}])) * sz[v]; // change to sum of sizes of followers..
            // cout << ans << '\n';
            // ans += (siz(st[v]) - mp[{u, v}]) * sz[u];
            ans += (siz(g2[v]) - (mp[{u, v}])) * sz[u];
            // cout << ans << '\n';
            ans -= mp[{u, v}] * sz[v];
            // cout << ans << '\n';
            ans -= mp[{v, u}] * sz[u];
            // cout << ans << '\n';
            merge(u, v);
        }
        cout << ans << '\n';
        // for (auto [pr, val] : mp) cout << pr.first << ' ' << pr.second << ' ' << val << '\n';
    }
}

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