oj.uz

Submission #936883

# Submission time Handle Problem Language Result Execution time Memory
936883 2024-03-03T01:28:37 Z Pring Making Friends on Joitter is Fun (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 ansE = 0, ansG = 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;
        ansE += SIZE(y);
        out_set[x].insert(y);
        in_set[y].insert(x);
        debug('+', x, y, ansE);
    }

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

    void MERGE(int x, int x_, int y, int y_) {
        ansG -= tri(SIZE(x_));
        ansG -= tri(SIZE(y));
        ansG += tri(SIZE(x_) + SIZE(y));
        { // IN MERGE
            if (in_set[x_].size() >= in_set[y].size()) {
                swap(x_, y);
            }
            ansE -= SIZE(y) * in_set[y].size();
            while (in_set[x_].size()) {
                int i = *in_set[x_].begin();
                ERASE(i, x_);
                q.push(mp(i, y));
            }
            in_agent.onion(x_, y);
            ansE += SIZE(y) * in_set[y].size();
            debug("ADD_Y", ansE);
        }
        // { // 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_);
        // }
    }

    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();
        debug(DS::ansE, DS::ansG);
        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

joitter2.cpp: In function 'void DS::INSERT(long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:69:9: note: in expansion of macro 'debug'
   69 |         debug('+', x, y, ansE);
      |         ^~~~~
joitter2.cpp: In function 'void DS::ERASE(long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:76:9: note: in expansion of macro 'debug'
   76 |         debug('-', x, y, ansE);
      |         ^~~~~
joitter2.cpp: In function 'void DS::MERGE(long long int, 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:95:13: note: in expansion of macro 'debug'
   95 |             debug("ADD_Y", ansE);
      |             ^~~~~
joitter2.cpp: In function 'void miku()':
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(DS::ansE, DS::ansG);
      |         ^~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -