Submission #936936

#	Time	Username	Problem	Language	Result	Execution time	Memory
936936		Pring	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	3 ms	11352 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;
    unordered_map<int, vector<int>> M[MXN];
    int deg[MXN];
    set<int> S[MXN];
    queue<pii> q;
    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 SET_EDGE(int t, int x, int y) {
        debug('+', t, y);
        deg[y]++;
        M[y][x].push_back(t);
        S[t].insert(y);
        ansE += SIZE(y);
    }

    void MERGE(int x, int y) {
        ansG -= tri(SIZE(x));
        ansG -= tri(SIZE(y));
        for (auto &i : M[x][y]) {
            ansE -= SIZE(x);
            S[i].erase(x);
            deg[x]--;
            debug('-', i, x);
        }
        M[x].erase(y);
        for (auto &i : M[y][x]) {
            ansE -= SIZE(y);
            S[i].erase(y);
            deg[y]--;
            debug('-', i, y);
        }
        M[y].erase(x);
        if (deg[x] >= deg[y]) swap(x, y);
        for (auto it = M[x].begin(); it != M[x].end(); it++) {
            for (auto &i : it -> sc) {
                ansE -= SIZE(x);
                S[i].erase(x);
                debug('-', i, x);
                q.push(mp(i, y));
            }
        }
        deg[x] = 0;
        ansE -= deg[y] * SIZE(y);
        M[x].clear();
        dsu.onion(x, y);
        ansE += deg[y] * SIZE(y);
        ansG += tri(SIZE(y));
    }

    void ADD_EDGE(int t, int y) {
        if (S[t].count(y)) return;
        int x = dsu.find(t);
        if (x == y) return;
        auto it = M[x].find(y);
        if (it == M[x].end() || it -> sc.empty()) {
            SET_EDGE(t, x, y);
            return;
        }
        MERGE(x, y);
    }

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

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

void miku() {
    int a, b;
    cin >> n >> m;
    DS::init(n);
    while (m--) {
        cin >> a >> b;
        DS::q.push(mp(a, b));
        DS::clear_queue();
        // DS::COUT();
        cout << DS::ansE + DS::ansG << '\n';
    }
}

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::SET_EDGE(long long int, long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:62:9: note: in expansion of macro 'debug'
   62 |         debug('+', t, y);
      |         ^~~~~
joitter2.cpp: In function 'void DS::MERGE(long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:76:13: note: in expansion of macro 'debug'
   76 |             debug('-', i, x);
      |             ^~~~~
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:83:13: note: in expansion of macro 'debug'
   83 |             debug('-', i, y);
      |             ^~~~~
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:91:17: note: in expansion of macro 'debug'
   91 |                 debug('-', i, x);
      |                 ^~~~~

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