oj.uz

Submission #524079

# Submission time Handle Problem Language Result Execution time Memory
524079 2022-02-08T15:26:38 Z bebecanvas Experimental Charges (NOI19_charges) C++14
18 / 100
 38 ms 11432 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]++;}
	}
	
	
}

signed main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	
	int n, q; cin >> n >> q;
	reset(n);
	
	vector<pair<int, int> > adj[100005];
	vector<pair<int, pair<int, int> > > v;
	for(int i=0; i<q; i++){
		char a; int b, c;
		cin >> a >> b >> c;
		if(a=='A'){adj[b].push_back(make_pair(c, 0)); adj[c].push_back(make_pair(b, 0)); v.push_back(make_pair(0, make_pair(b, c)));}
		else if(a=='R'){adj[b].push_back(make_pair(c, 1)); adj[c].push_back(make_pair(b, 0)); v.push_back(make_pair(0, make_pair(b, c)));}
		else{v.push_back(make_pair(1, make_pair(b, c)));}
	}
	
	int charge[100005]={0};
	int visited[100005]={0};
	for(int i=1; i<=n; i++){
		if(visited[i]){continue;}
		//cout << "i " << i << endl;
		queue<int> q;
		q.push(i);
		visited[i]=1;
		while(!q.empty()){
			int cur= q.front(); q.pop();
			//cout << "cur " << cur << endl;
			//cout << charge[cur] << endl;
			for(auto ii: adj[cur]){
				int a= ii.first;
				int b= ii.second;
				//cout << a << " " << b << endl;
				if(visited[a]){continue;}
				visited[a]=1;
				if(b==1){charge[a]=charge[cur];}
				else{charge[a]=charge[cur]+1; charge[a]%=2;}
				//cout << charge[a] << endl;
				q.push(a);
			}
		}
	}
	//for(int i=1; i<=n; i++){cout << charge[i] << " ";} cout << endl;
	for(auto i: v){
		int a= i.first;
		int b= i.second.first;
		int c= i.second.second;
		//cout << a << " " << b << " " << c << endl;
		if(a){
			int bb= findSet(b);
			int cc= findSet(c);
			//cout << b << " " << c << endl;
			if(bb==cc){
				if(charge[b]==charge[c]){cout << "R" << endl;}
				else{cout << "A" << endl;}
			}else{cout << "?" << endl;}
		}else{unionSet(b, c);}
	}
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 2 ms 4172 KB Output is correct
5 Correct 2 ms 4228 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11152 KB Output is correct
2 Correct 33 ms 11432 KB Output is correct
3 Correct 32 ms 10108 KB Output is correct
4 Correct 35 ms 11112 KB Output is correct
5 Correct 38 ms 11264 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11008 KB Output is correct
2 Incorrect 35 ms 10924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10992 KB Output is correct
2 Incorrect 36 ms 10936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 2 ms 4172 KB Output is correct
5 Correct 2 ms 4228 KB Output is correct
6 Correct 3 ms 4236 KB Output is correct
7 Incorrect 3 ms 4240 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 2 ms 4172 KB Output is correct
5 Correct 2 ms 4228 KB Output is correct
6 Correct 33 ms 11152 KB Output is correct
7 Correct 33 ms 11432 KB Output is correct
8 Correct 32 ms 10108 KB Output is correct
9 Correct 35 ms 11112 KB Output is correct
10 Correct 38 ms 11264 KB Output is correct
11 Correct 31 ms 11008 KB Output is correct
12 Incorrect 35 ms 10924 KB Output isn't correct
13 Halted 0 ms 0 KB -