Submission #971367

#	Time	Username	Problem	Language	Result	Execution time	Memory
971367		vjudge1	Experimental Charges (NOI19_charges)	C++14	100 / 100	21 ms	3420 KiB

charges

/*
 * Created at 1:32 PM on 30 Mar 2024
 */

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>

#ifdef LOCAL
#include "debug.h"
#else
#define trace(...) 42
#endif

struct DSU {
private:
    std::size_t n;
    std::vector<size_t> link;
    std::vector<int> size;

    std::vector<int> flipped;

public:
    explicit DSU(const size_t n_) : n(n_),
                                    size(n_, 1), link(n_),
                                    flipped(n_, 0) {
        std::iota(link.begin(), link.end(), 0);
    }

    std::size_t find(std::size_t x) const {
        while (x != link[x]) {
            x = link[x];
        }
        return x;
    }

    int find_charge(std::size_t x) const {
        auto res = flipped[x];
        while (x != link[x]) {
            x = link[x];
            res ^= flipped[x];
        }
        return res;
    }

    enum class InteractionType {
        attract,
        repel,
        uncertain
    };

    bool unite(std::size_t x, std::size_t y, const InteractionType it) {
        assert(it != InteractionType::uncertain);

        bool flip = it == InteractionType::attract and find_charge(x) == find_charge(y);
        flip |= it == InteractionType::repel and find_charge(x) != find_charge(y);

        x = find(x);
        y = find(y);

        if (x == y) {
            assert(!flip);
            return false;
        }

        if (size[x] < size[y]) {
            std::swap(x, y);
        }

        trace(x, y, flip);

        flipped[y] ^= flip; // TODO: checks?
        link[y] = x;
        size[x] += size[y];

        return true;
    }

    InteractionType interact(const std::size_t x, const std::size_t y) const {
        if (find(x) != find(y)) {
            return InteractionType::uncertain;
        }

        return find_charge(x) != find_charge(y) ? InteractionType::attract : InteractionType::repel;
    }
};

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n, q;
    std::cin >> n >> q;

    DSU dsu(n);

    while (q--) {
        char op;
        std::cin >> op;

        std::size_t a, b;
        std::cin >> a >> b;
        --a, --b;

        if (op == 'A') {
            dsu.unite(a, b, DSU::InteractionType::attract);
        } else if (op == 'R') {
            dsu.unite(a, b, DSU::InteractionType::repel);
        } else if (op == 'Q') {
            char ans;

            switch (dsu.interact(a, b)) {
                case DSU::InteractionType::attract:
                    ans = 'A';
                    break;
                case DSU::InteractionType::repel:
                    ans = 'R';
                    break;
                case DSU::InteractionType::uncertain:
                    ans = '?';
                    break;
            }

            std::cout << ans << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

charges.cpp: In constructor 'DSU::DSU(size_t)':
charges.cpp:26:22: warning: 'DSU::size' will be initialized after [-Wreorder]
   26 |     std::vector<int> size;
      |                      ^~~~
charges.cpp:25:25: warning:   'std::vector<long unsigned int> DSU::link' [-Wreorder]
   25 |     std::vector<size_t> link;
      |                         ^~~~
charges.cpp:31:14: warning:   when initialized here [-Wreorder]
   31 |     explicit DSU(const size_t n_) : n(n_),
      |              ^~~
charges.cpp: In member function 'bool DSU::unite(std::size_t, std::size_t, DSU::InteractionType)':
charges.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define trace(...) 42
      |                    ^~
charges.cpp:77:9: note: in expansion of macro 'trace'
   77 |         trace(x, y, flip);
      |         ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31