Submission #674730

#	Time	Username	Problem	Language	Result	Execution time	Memory
674730		vuavisao	Experimental Charges (NOI19_charges)	C++14	100 / 100	50 ms	8388 KiB

charges

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

template<typename Lhs, typename Rhs> inline void Max_self(Lhs &a, Rhs b) { a = (a > b ? a : b); }
template<typename Lhs, typename Rhs> inline void Min_self(Lhs &a, Rhs b) { a = (a < b ? a : b); }

const int N = 1e5 + 10;
const char Res[] = {'A', 'R', '?'};

struct dsu {
    vector<int> parent = {};

    void resize(int _n) { parent.resize(_n + 10); for(int i = 1; i <= _n; ++ i) parent[i] = i; }

    dsu() {};
    dsu(int n) { this -> resize(n); }

    int ancestor(int u) {
        if(parent[u] == u) return u;
        return parent[u] = ancestor(parent[u]);
    }

    void join(int u, int v) {
        u = ancestor(u), v = ancestor(v);
        if(u == v) return;
        parent[v] = u;
    }
};

struct state {
    int v = 0;
    int mask = 0;
    state() {};
    state(int _v, int _mask) { v = _v; mask = _mask; };
};

int n, q;
vector<state> g[N];
char qq[N];
pair<int, int> couple[N];

bool visited[N];
bool have[N];

void dfs(int u) {
    visited[u] = true;
    for(const auto& psy : g[u]) {
        int v = psy.v, mask = psy.mask;
        if(visited[v]) continue;
        visited[v] = true;
        have[v] = have[u] ^ mask;
        dfs(v);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("NOI19_charges.inp", "r")) {
        freopen("NOI19_charges.inp", "r", stdin);
        freopen("NOI19_charges.out", "w", stdout);
    }
    cin >> n >> q;
    for(int i = 1; i <= q; ++ i) {
        int u, v; cin >> qq[i] >> u >> v;
        couple[i] = make_pair(u, v);
        if(qq[i] == 'Q') continue;
        int mask = 0;
        if(qq[i] == 'A') mask = 1;
        g[u].push_back(state(v, mask));
        g[v].push_back(state(u, mask));
    }
    for(int i = 1; i <= n; ++ i) {
        if(visited[i]) continue;
        dfs(i);
    }
    dsu dsu(n);
    for(int i = 1; i <= q; ++ i) {
        const auto& psy = couple[i];
        int u = psy.first, v = psy.second;
        if(qq[i] != 'Q') {
            dsu.join(u, v);
        }
        else {
            int res = 2;
            if(dsu.ancestor(u) == dsu.ancestor(v)) {
                res = (have[u] == have[v]);
            }
            cout << Res[res] << '\n';
        }
    }
    return 0;
}

/// Code by vuavisao

Compilation message (stderr)

charges.cpp: In function 'int32_t main()':
charges.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen("NOI19_charges.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
charges.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen("NOI19_charges.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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