제출 #797020

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

joitter2

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 100100;
const int mod = 1e9 + 7;

using namespace std;

long long res;

int n;
int p[N];
int sz[N];
set<int> S[N];
set<int> A[N], B[N];
queue<pair<int, int>> q;

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

void upd(int X, int Y) {
    A[X].insert(Y);
    B[Y].insert(X);
    if (A[Y].find(X) != A[Y].end()) {
        q.push({X, Y});
    }
}

void solve(int X, int Y)
{
    X = get(X);
    Y = get(Y);
    if (X == Y) {
        return;
    }
    if (S[X].size() < S[Y].size()) {
        swap(X, Y);
    }
    res += 1ll * sz[X] * S[Y].size() + 1ll * sz[Y] * S[X].size();
    p[Y] = X;
    sz[X] += sz[Y];
    for (int z: S[Y]) {
        if (S[X].find(z) == S[X].end()) {
            S[X].insert(z);
        } else {
            res -= sz[X];
        }
    }
    A[X].erase(Y);
    B[X].erase(Y);
    A[Y].erase(X);
    B[Y].erase(X);
    for (int z: A[Y]) {
        upd(X, z);
    }
    for (int z: B[Y]) {
        upd(z, X);
    }
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
        S[i].insert(i);
    }

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        int X = get(x);
        int Y = get(y);
        if (X != Y && S[Y].find(x) == S[Y].end()) {
            res += sz[Y];
            S[Y].insert(x);
            upd(X, Y);
            while (!q.empty()) {
                solve(q.front().fi, q.front().se);
                q.pop();
            }
        }
        cout << res << "\n";
    }
}

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