Submission #663244

#	Time	Username	Problem	Language	Result	Execution time	Memory
663244		arujbansal	Experimental Charges (NOI19_charges)	C++17	100 / 100	28 ms	2504 KiB

charges

#include <bits/stdc++.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

using ll = long long;

template<typename S, typename T> void smax(S &a, const T &b) { if (a < b) a = b; }
template<typename S, typename T> void smin(S &a, const T &b) { if (a > b) a = b; }

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;

struct UFDS {
    int n;
    vector<int> info;
 
    UFDS() {}
 
    UFDS(int _n) { init(_n); }
 
    void init(int _n) {
        n = _n;
        info.assign(n, -1);
    }
 
    int get(int x) {
        if (info[x] < 0) return x;
        return info[x] = get(info[x]);
    }
 
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
 
        if (info[x] > info[y])
            swap(x, y);
 
        info[x] += info[y];
        info[y] = x;
 
        return true;    
    }
 
    bool connected(int x, int y) { return get(x) == get(y); }
};
 
struct two_colouring {
    int n;
    UFDS ufds;
    vector<int> answer, in_answer;
 
    two_colouring(int _n) { init(_n); }
 
    void init(int _n) {
        n = _n;
        ufds.init(2 * n);
    }
 
    void add_clause_equal(int x, int y) {
        ufds.unite(x, y);
        ufds.unite(x + n, y + n);
    }
 
    void add_clause_opposite(int x, int y) {
        ufds.unite(x, y + n);
        ufds.unite(x + n, y);
    }
 
    bool satisfiable() {
        for (int i = 0; i < n; i++)
            if (ufds.connected(i, i + n)) return false;
 
        return true;
    }
    
    // Construct an answer where we minimise the number of "which" values in each component
    // which is either 1 or 0
    void construct_answer(int which) {
        answer.resize(n);
        in_answer.assign(2 * n, 0);
        vector<int> cnt(2 * n, 0);

        for (int i = 0; i < 2 * n; i++) 
            cnt[ufds.get(i)] += (i > n) ^ which;

        for (int i = 0; i < n; i++) {
            int cur = ufds.get(i), complement = ufds.get(i + n);

            if (in_answer[cur] || in_answer[complement])
                continue;

            if (cnt[cur] < cnt[complement])
                in_answer[cur] = true;
            else 
                in_answer[complement] = true;
        }

        for (int i = 0; i < n; i++)
            answer[i] = (in_answer[ufds.get(i)] ? 1 : 0);
    }
};

void solve() {
    int N, Q;
    cin >> N >> Q;

    two_colouring solver(N);
    while (Q--) {
        char t;
        int a, b;
        cin >> t >> a >> b;
        a--, b--;

        if (t == 'A') solver.add_clause_opposite(a, b);
        else if (t == 'R') solver.add_clause_equal(a, b);
        else {
            if (solver.ufds.connected(a, b)) cout << "R\n";
            else if (solver.ufds.connected(a, b + N)) cout << "A\n";
            else cout << "?\n"; 
        }   
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

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