oj.uz

Submission #524077

# Submission time Handle Problem Language Result Execution time Memory
524077 2022-02-08T15:25:33 Z bebecanvas Experimental Charges (NOI19_charges) C++14
25 / 100
 39 ms 11132 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)); v.push_back(make_pair(0, make_pair(b, c)));}
		else if(a=='R'){adj[b].push_back(make_pair(c, 1)); 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
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 Incorrect 2 ms 4172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9740 KB Output is correct
2 Correct 25 ms 9940 KB Output is correct
3 Correct 28 ms 9624 KB Output is correct
4 Correct 28 ms 9556 KB Output is correct
5 Correct 27 ms 9684 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10240 KB Output is correct
2 Correct 35 ms 10004 KB Output is correct
3 Correct 38 ms 9592 KB Output is correct
4 Correct 39 ms 10100 KB Output is correct
5 Correct 39 ms 9856 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10308 KB Output is correct
2 Incorrect 37 ms 11132 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 Incorrect 2 ms 4172 KB Output isn't correct
5 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 Incorrect 2 ms 4172 KB Output isn't correct
5 Halted 0 ms 0 KB -