Submission #937081

#	Time	Username	Problem	Language	Result	Execution time	Memory
937081		Pring	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	810 ms	90072 KiB

joitter2

#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 dsu;
    int deg_in[MXN], deg_out[MXN];
    queue<pii> q;
    set<pii> out[MXN];
    unordered_map<int, vector<int>> M[MXN];
    set<int> S[MXN];
    int ansE = 0, ansG = 0;

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

    int SIZE(int X) {
        return -dsu.p[X];
    }

    void init(int n) {
        dsu.init(n);
    }

    void ADD_EDGE(int x, int X, int Y) {
        deg_in[Y]++;
        deg_out[X]++;
        out[X].insert(mp(x, Y));
        M[Y][X].push_back(x);
        S[x].insert(Y);
        ansE += SIZE(Y);
        // debug('+', x, Y, ansE);
    }

    void ERASE_EDGE(int x, int X, int Y) {
        deg_out[X]--;
        deg_in[Y]--;
        out[X].erase(mp(x, Y));
        S[x].erase(Y);
        ansE -= SIZE(Y);
        // debug('-', x, Y, ansE);
    }

    void MERGE(int X, int Y) {
        ansG -= tri(SIZE(X));
        ansG -= tri(SIZE(Y));
        ansG += tri(SIZE(X) + SIZE(Y));
        for (auto &i : M[X][Y]) ERASE_EDGE(i, Y, X);
        M[X].erase(Y);
        for (auto &i : M[Y][X]) ERASE_EDGE(i, X, Y);
        M[Y].erase(X);
        if (deg_in[X] + deg_out[X] >= deg_in[Y] + deg_out[Y]) swap(X, Y);
        // debug("MERGE", X, Y);
        {
            for (auto it = M[X].begin(); it != M[X].end(); it++) {
                for (auto &i : it -> sc) {
                    ERASE_EDGE(i, dsu.find(i), X);
                    q.push(mp(i, Y));
                }
            }
            M[X].clear();
        }
        {
            vector<pii> v;
            for (auto i : out[X]) v.push_back(i);
            for (auto i : v) {
                ERASE_EDGE(i.fs, X, i.sc);
                q.push(mp(i.fs, i.sc));
            }
            for (auto i : v) {
                M[i.sc][X].clear();
            }
            out[X].clear();
            // debug("CLEAR", X);
        }
        ansE -= SIZE(Y) * deg_in[Y];
        dsu.onion(X, Y);
        ansE += SIZE(Y) * deg_in[Y];
    }

    void TEST(int x, int Y) {
        if (S[x].find(Y) != S[x].end()) return;
        int X = dsu.find(x);
        auto it = M[X].find(Y);
        if (it == M[X].end() || it -> sc.empty()) {
            ADD_EDGE(x, X, Y);
            return;
        }
        MERGE(X, Y);
    }

    void clear_queue() {
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            if (dsu.find(x) == dsu.find(y)) continue;
            TEST(x, dsu.find(y));
        }
    }

    void COUT() {
        cout << endl;
        FOR(i, 1, n + 1) {
            cout << i << ": ";
            // for (auto j : S[i]) cout << j << ' ';
            for (auto it = M[i].begin(); it != M[i].end(); it++) {
                cout << '[' << it -> fs << ":";
                for (auto &j : it -> sc) cout << ' ' << j;
                cout << "] ";
            }
            cout << endl;
        }
        debug(ansE, ansG);
        cout << endl;
    }
}

void miku() {
    int a, b;
    cin >> n >> m;
    // cin >> n;
    DS::init(n);
    while (m--) {
        cin >> a >> b;
    // while (cin >> a >> b) {
        DS::q.push(mp(a, b));
        DS::clear_queue();
        // DS::COUT();
        cout << DS::ansE + DS::ansG << '\n';
        // for (auto &i : DS::out[5]) cout << '<' << i.fs << ' ' << i.sc << "> ";
        // cout << endl;
    }
}

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

Compilation message (stderr)

joitter2.cpp: In function 'void DS::COUT()':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:150:9: note: in expansion of macro 'debug'
  150 |         debug(ansE, ansG);
      |         ^~~~~

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