Submission #1284941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284941		quanlm	Experimental Charges (NOI19_charges)	C++20	32 / 100	16 ms	3604 KiB

charges

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define oo 1e18
#define pb push_back
#define ii pair<int, int>
#define iii pair<int, ii>
#define TASK "AR"

const int N = 100005;

int n, q;
pair<char, ii> Q[N];

namespace sub1 {
    int e[N];

    bool check() {
        return n == 2 && q <= 10;
    }

    void solve() {
        for (int i = 1; i <= q; i++) {
            char type = Q[i].fi;
            int a = Q[i].se.fi, b = Q[i].se.se;

            if (type == 'A') {
                if (e[a] == 0) {
                    if (e[b] == 0) e[a] = 1, e[b] = -1;
                    else e[a] = -e[b];
                } else if (e[b] == 0) {
                    if (e[a] == 0) e[a] = 1, e[b] = -1;
                    else e[b] = -e[a];
                } else if (e[a] == e[b]) {
                    e[b] = -e[a];
                }
            } else if (type == 'R') {
                if (e[a] == 0 && e[b] == 0) {
                    e[a] = e[b] = 1;
                } else if (e[a] != e[b]) {
                    if (e[a] != 0) e[b] = e[a];
                    else e[a] = e[b];
                }
            } else {
                if (e[a] == 0 || e[b] == 0) cout << "?\n";
                else if (e[a] == e[b]) cout << "R\n";
                else cout << "A\n";
            }
        }
    }
}

namespace sub2 {
    bool check() {
        for (int i = 1; i <= q; i++)
            if (Q[i].se.fi > 1 || Q[i].se.se > 1) return 0;
        return 1;
    }
}

namespace sub3 {
    int par[N];

    bool check() {
        for (int i = 1; i <= q; i++)
            if (Q[i].fi == 'A') return 0;
        return 1;
    }

    int acs(int u) {
        if (u == par[u]) return u;
        return par[u] = acs(par[u]);
    }

    void join(int u, int v) {
        int x = acs(u), y = acs(v);
        if (x != y) par[x] = y;
    }

    void solve() {
        for (int i = 1; i <= n; i++) par[i] = i;

        for (int i = 1; i <= q; i++) {
            char type = Q[i].fi;
            int a = Q[i].se.fi, b = Q[i].se.se;

            if (type == 'R') {
                join(a, b);
            } else {
                cout << (acs(a) == acs(b) ? 'R' : '?') << '\n';
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    cin >> n >> q;

    for (int i = 1; i <= q; i++) cin >> Q[i].fi >> Q[i].se.fi >> Q[i].se.se;

    if (sub3::check()) sub3::solve();
    else if (sub1::check()) sub1::solve();
    else if (sub2::check()) sub1::solve();
    else sub1::solve();
}

Compilation message (stderr)

charges.cpp: In function 'int main()':
charges.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
charges.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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