oj.uz

Submission #477173

# Submission time Handle Problem Language Result Execution time Memory
477173 2021-10-01T01:54:51 Z sumit_kk10 Experimental Charges (NOI19_charges) C++14
100 / 100
 77 ms 31128 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 13 ms 23712 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 28788 KB Output is correct
2 Correct 59 ms 28984 KB Output is correct
3 Correct 43 ms 28276 KB Output is correct
4 Correct 46 ms 28908 KB Output is correct
5 Correct 48 ms 28996 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31128 KB Output is correct
2 Correct 48 ms 30112 KB Output is correct
3 Correct 53 ms 28972 KB Output is correct
4 Correct 63 ms 30008 KB Output is correct
5 Correct 77 ms 29720 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31024 KB Output is correct
2 Correct 51 ms 30280 KB Output is correct
3 Correct 55 ms 29392 KB Output is correct
4 Correct 62 ms 29896 KB Output is correct
5 Correct 68 ms 29824 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 13 ms 23712 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 14 ms 23780 KB Output is correct
7 Correct 16 ms 23932 KB Output is correct
8 Correct 13 ms 23772 KB Output is correct
9 Correct 13 ms 23760 KB Output is correct
10 Correct 15 ms 23812 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 13 ms 23712 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 48 ms 28788 KB Output is correct
7 Correct 59 ms 28984 KB Output is correct
8 Correct 43 ms 28276 KB Output is correct
9 Correct 46 ms 28908 KB Output is correct
10 Correct 48 ms 28996 KB Output is correct
11 Correct 49 ms 31128 KB Output is correct
12 Correct 48 ms 30112 KB Output is correct
13 Correct 53 ms 28972 KB Output is correct
14 Correct 63 ms 30008 KB Output is correct
15 Correct 77 ms 29720 KB Output is correct
16 Correct 47 ms 31024 KB Output is correct
17 Correct 51 ms 30280 KB Output is correct
18 Correct 55 ms 29392 KB Output is correct
19 Correct 62 ms 29896 KB Output is correct
20 Correct 68 ms 29824 KB Output is correct
21 Correct 14 ms 23780 KB Output is correct
22 Correct 16 ms 23932 KB Output is correct
23 Correct 13 ms 23772 KB Output is correct
24 Correct 13 ms 23760 KB Output is correct
25 Correct 15 ms 23812 KB Output is correct
26 Correct 48 ms 31044 KB Output is correct
27 Correct 51 ms 29912 KB Output is correct
28 Correct 61 ms 29600 KB Output is correct
29 Correct 60 ms 29612 KB Output is correct
30 Correct 62 ms 29768 KB Output is correct