Submission #477173

#	Time	Username	Problem	Language	Result	Execution time	Memory
477173		sumit_kk10	Experimental Charges (NOI19_charges)	C++14	100 / 100	77 ms	31128 KiB

charges

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
vector<pair<int, int> > graph[N];
int component[N], col[N], vis[N];

void dfs(int node, int color){
	if(vis[node] == true)
		return;
	vis[node] = true;
	col[node] = color;
	for(auto k : graph[node]){
		if(!vis[k.first]){
			if(k.second == 0)
				dfs(k.first, color);
			else
				dfs(k.first, (color == 1 ? 2 : 1));
		}
	}
}

int find(int x){
	while(true){
		if(x == component[x])
			return x;
		component[x] = component[component[x]];
		x = component[x];
	}
}

void merge(int a, int b){
	int u = find(a), v = find(b);
	component[u] = component[v];
}

void solve(){
	int n, m;
	cin >> n >> m;
	int u[m], v[m];
	char x[m];
	vector<char> ans;
	for(int i = 1; i <= n; ++i)
		component[i] = i;
	for(int j = 0; j < m; ++j){
		cin >> x[j] >> u[j] >> v[j];
		if(x[j] == 'R'){
			merge(u[j], v[j]);
			graph[u[j]].push_back({v[j], 0});
			graph[v[j]].push_back({u[j], 0});
		}
		else if(x[j] == 'A'){
			merge(u[j], v[j]);
			graph[u[j]].push_back({v[j], 1});
			graph[v[j]].push_back({u[j], 1});
		}
		else{
			if(find(u[j]) != find(v[j]))
				ans.push_back('?');
			else
				ans.push_back('p');
		}
	}
	for(int i = 1; i <= n; ++i)
		if(!vis[i])
			dfs(i, 1);
	int ct = 0;
	for(int i = 0; i < m; ++i){
		if(x[i] == 'Q'){
			if(ans[ct] != '?'){
			    if(find(u[i]) != find(v[i])) ans[ct] = '?';
				else if(col[u[i]] == col[v[i]]) ans[ct] = 'R';
				else ans[ct] = 'A';
		    }
		    ++ct;
		}
	}
	for(auto k : ans)
		cout << k << '\n';
}

int main(){
	fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

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