Submission #689861

#	Time	Username	Problem	Language	Result	Execution time	Memory
689861		sudheerays123	Experimental Charges (NOI19_charges)	C++17	100 / 100	28 ms	3356 KiB

charges

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 2e5+5 , INF = 1e18 , MOD = 1e9+7;

vector<ll> par(N);

void make_set(ll n){
	for(ll i = 1; i <= n; i++){
		par[i] = i;
	}
}

ll find(ll x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}

void unite(ll a , ll b){
	a = find(a);
	b = find(b);

	if(a == b) return;

	par[b] = a;
}

void solve(){

	ll n,q;
	cin >> n >> q;

	make_set(2*n);

	while(q--){
		char x;
		ll a,b;
		cin >> x >> a >> b;

		if(x == 'R'){
			unite(a,b);
			unite(a+n,b+n);
		}
		else if(x == 'A'){
			unite(a+n,b);
			unite(a,b+n);
		}
		else{
			if(find(a) == find(b) || find(a+n) == find(b+n)){
				cout << "R\n";
			}
			else if(find(a+n) == find(b) || find(a) == find(b+n)){
				cout << "A\n";
			}
			else cout << "?\n";
		}
	}


	
}

int main(){

	fast;

	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();

	return 0;
}

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