Submission #524080

#	Time	Username	Problem	Language	Result	Execution time	Memory
524080		bebecanvas	Experimental Charges (NOI19_charges)	C++14	100 / 100	53 ms	13372 KiB

charges

#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, 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: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31