oj.uz

답안 #936871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936871 2024-03-03T00:49:32 Z Pring 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 2 ms 10844 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 100005;
int n, m;

struct DSU {
    int p[MXN];
    void init(int n) {
        fill(p + 1, p + n + 1, -1);
    }
    int find(int x) {
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool onion(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        p[y] += p[x];
        p[x] = y;
        return true;
    }
};

namespace DS {
    DSU in_agent, out_agent;
    set<int> in_set[MXN], out_set[MXN];
    queue<pii> q;
    int ans = 0;

    void init(int n) {
        in_agent.init(n);
        out_agent.init(n);
    }

    int tri(int x) {
        return x * (x - 1);
    }

    int SIZE(int x) {
        return -in_agent.p[x];
    }

    bool FIND(int x, int y) {
        return out_set[x].find(y) != out_set[x].end();
    }

    void INSERT(int x, int y) {
        if (FIND(x, y)) return;
        ans += SIZE(y);
        out_set[x].insert(y);
        in_set[y].insert(x);
    }

    void ERASE(int x, int y) {
        ans -= SIZE(y);
        out_set[x].erase(y);
        in_set[y].erase(x);
    }

    void MERGE(int x, int x_, int y, int y_) {
        ans -= tri(SIZE(x_));
        ans -= tri(SIZE(y));
        ans -= SIZE(x_) * in_set[x_].size();
        ans -= SIZE(y) * in_set[y].size();
        { // IN MERGE
            if (in_set[x_].size() >= in_set[y].size()) {
                swap(x_, y);
            }
            while (in_set[x_].size()) {
                int i = *in_set[x_].begin();
                ERASE(i, x_);
                q.push(mp(i, y_));
            }
            in_agent.onion(x_, y);
        }
        { // OUT_MERGE
            if (out_set[x].size() >= out_set[y_].size()) {
                swap(x, y_);
            }
            while (out_set[x].size()) {
                int i = *out_set[x].begin();
                ERASE(x, i);
                q.push(mp(y_, i));
            }
            out_agent.onion(x, y_);
        }
        ans += tri(SIZE(y));
        ans += SIZE(y) * in_set[y].size();
    }

    void clear_queue() {
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            int x_ = in_agent.find(x), y_ = out_agent.find(y);
            if (FIND(y_, x_)) {
                ERASE(y_, x_);
                MERGE(x, x_, y, y_);
            } else {
                INSERT(x, y);
            }
        }
    }

    void ADD(int x, int y) {
        if (in_agent.find(x) == in_agent.find(y)) return;
        x = out_agent.find(x);
        y = in_agent.find(y);
        q.push(mp(x, y));
        clear_queue();
    }

    void COUT() {
        cout << "in : ";
        FOR(i, 1, n + 1) cout << in_agent.find(i) << ' ';
        cout << endl;
        cout << "out: ";
        FOR(i, 1, n + 1) cout << out_agent.find(i) << ' ';
        cout << endl;
    }
}

void miku() {
    int a, b;
    cin >> n >> m;
    DS::init(n);
    while (m--) {
        cin >> a >> b;
        DS::ADD(a, b);
        // DS::COUT();
        cout << DS::ans << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -