oj.uz

Submission #517526

# Submission time Handle Problem Language Result Execution time Memory
517526 2022-01-23T05:47:21 Z bebecanvas Experimental Charges (NOI19_charges) C++14
32 / 100
 46 ms 4884 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'

int p[1000005];
int h[1000005];

void reset(int N){
	for(int i=0; i<=N; i++){
		p[i]=i;
		h[i]=1;
	}
}

int findSet(int u){
	if(u==p[u]){return u;}
	else{
		p[u]= findSet(p[u]);
		return p[u];
	}
}

void unionSet(int a, int b){
	int A= findSet(a);
	int B= findSet(b);
	if(A==B){return;}
	
	if(h[A]<h[B]){
		p[A]=B;
	}else{
		p[B]=A;
		if(h[A]==h[B]){h[A]++;}
	}
}

int p2[1000005];
int h2[1000005];

void reset2(int N){
	for(int i=0; i<=N; i++){
		p2[i]=i;
		h2[i]=1;
	}
}

int findSet2(int u){
	if(u==p2[u]){return u;}
	else{
		p2[u]= findSet2(p2[u]);
		return p2[u];
	}
}

void unionSet2(int a, int b){
	int A= findSet2(a);
	int B= findSet2(b);
	if(A==B){return;}
	
	if(h2[A]<h2[B]){
		p2[A]=B;
	}else{
		p2[B]=A;
		if(h2[A]==h2[B]){h2[A]++;}
	}
}

signed main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q; cin >> n >> q;
    reset(n); reset2(n);
    
    for(int i=0; i<q; i++){
		char a; cin >> a;
		int b, c; cin >> b >> c;
		if(a=='A'){unionSet2(b, c);}
		else if(a=='R'){unionSet2(b, c); unionSet(b, c);}
		else{
			int bb= findSet(b);
			int cc= findSet(c);
			if(bb==cc){cout<< "R" << endl; continue;}
			
			bb= findSet2(b);
			cc= findSet2(c);
			if(bb==cc){cout<< "A" << endl; continue;}
			
			cout << "?" << endl;
		}

	} 
  
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4176 KB Output is correct
2 Correct 22 ms 4220 KB Output is correct
3 Correct 46 ms 4240 KB Output is correct
4 Correct 43 ms 4200 KB Output is correct
5 Correct 28 ms 4236 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4852 KB Output is correct
2 Correct 32 ms 4704 KB Output is correct
3 Correct 32 ms 4680 KB Output is correct
4 Correct 29 ms 4776 KB Output is correct
5 Correct 35 ms 4884 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 4588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 22 ms 4176 KB Output is correct
7 Correct 22 ms 4220 KB Output is correct
8 Correct 46 ms 4240 KB Output is correct
9 Correct 43 ms 4200 KB Output is correct
10 Correct 28 ms 4236 KB Output is correct
11 Correct 42 ms 4852 KB Output is correct
12 Correct 32 ms 4704 KB Output is correct
13 Correct 32 ms 4680 KB Output is correct
14 Correct 29 ms 4776 KB Output is correct
15 Correct 35 ms 4884 KB Output is correct
16 Incorrect 33 ms 4588 KB Output isn't correct
17 Halted 0 ms 0 KB -