Submission #647497

#TimeUsernameProblemLanguageResultExecution timeMemory
647497LeonaRagingExperimental Charges (NOI19_charges)C++14
32 / 100
44 ms8464 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back #define db(val) "[" #val " = " << (val) << "] " const ll mod = 1e9 + 7; const int maxn = 1e5 + 4; const int INF = 1e9; int n, q, sign[maxn]; struct DisjointSet { int par[maxn]; vector<int> mySet[maxn]; DisjointSet(int n) { for (int i = 1; i <= n; i++) par[i] = i, mySet[i].pb(i); } int find(int x) { if (x != par[x]) par[x] = find(par[x]); return par[x]; } bool join(int u, int v, int type) { u = find(u); v = find(v); if (u == v) return 0; if (mySet[v].size() > mySet[u].size()) swap(mySet[u], mySet[v]); for (int x : mySet[v]) { if (type == 1) sign[x] ^= 1; mySet[u].pb(x); } mySet[v].clear(); par[v] = u; return 1; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(".INP", "r", stdin); //freopen(".OUT", "w", stdout); cin >> n >> q; memset(sign, 1, sizeof sign); DisjointSet Dsu(n); for (int i = 1; i <= q; i++) { char type; int u, v; cin >> type >> u >> v; if (type == 'Q') { if (Dsu.find(u) != Dsu.find(v)) cout << '?'; else cout << (sign[u] == sign[v] ? 'R' : 'A'); cout << '\n'; } else Dsu.join(u, v, (type == 'R' ? 0 : 1)); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...