Submission #518539

#	Time	Username	Problem	Language	Result	Execution time	Memory
518539		thegrimbee	Experimental Charges (NOI19_charges)	C++14	100 / 100	36 ms	4848 KiB

charges

#include <bits/stdc++.h>
#define int long long
using namespace std;
int p[2*1000005]; ///parent
int height[1000005]; ///height

void reset(int N){
	for(int i = 0;i <= N;i++){
		p[i] = i; ///all sets are disjoint
		height[i] = 1;
	}
}

int findSet(int u){
	if(u == p[u]) return u; ///representative
	else{
		p[u] = findSet(p[u]); ///search upwards
		return p[u];
	}
}

void unionSet(int a, int b){
	///find represenative of a and b
	int A = findSet(a);
	int B = findSet(b);
	
	if(A == B) return;
	
	if(height[A] < height[B]){
		p[A] = B;
	}
	else{
		p[B] = A;
		if(height[A] == height[B]) height[A]++;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);		
	int N, Q;
	char T;
	int a , b, temp1, temp2, temp3, temp4;
	cin >> N >> Q;
	reset(2*(N+1));
	for (int i = 0; i < Q; ++i){
		cin >> T >> a >> b;
		if (T == 'Q'){
			temp1 = findSet(a);
			temp2 = findSet(b);
			temp3 = findSet(a+N);
			temp4 = findSet(b+N);
			if (temp1 == temp2 && temp1 == temp4)cout << "?\n";
			else if (temp1 == temp2)cout << "R\n";
			else if (temp1 == temp4)cout << "A\n";
			else cout << "?\n";
		}
		else if (T == 'A'){
			unionSet(a, b + N);
			unionSet(a+N, b);
		}
		else{
			unionSet(a, b);
			unionSet(a+N, b+N);
		}
	}
	
}

Compilation message (stderr)

charges.cpp: In function 'int main()':
charges.cpp:42:27: warning: variable 'temp3' set but not used [-Wunused-but-set-variable]
   42 |  int a , b, temp1, temp2, temp3, temp4;
      |                           ^~~~~

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