oj.uz

Submission #518342

# Submission time Handle Problem Language Result Execution time Memory
518342 2022-01-23T12:55:16 Z thegrimbee Experimental Charges (NOI19_charges) C++14
7 / 100
 1000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);		
	int N, Q;
	char T;
	int a , b;
	cin >> N >> Q;
	vector<vector<vector<int>>> adj(N+1, vector<vector<int>>(2)); 
	pair <int, int> temp;
	vector<int> visited(N+1, -1);
	queue<pair<int, int>> q;
	for (int i = 0; i < Q; ++i){
		cin >> T >> a >> b;
		if (T == 'R'){adj[a][0].push_back(b);adj[b][0].push_back(a);}
		else if (T == 'A'){adj[a][1].push_back(b);adj[b][1].push_back(a);}
		else{
			visited = vector<int>(N+1, -1);
			q.push({a, 0});
			visited[a] = 0;
			while (!q.empty() && visited[b] == -1){
				temp = q.front();
				q.pop();
				
				for (int i = 0; i < (int)adj[temp.first][0].size(); ++i){
					if (visited[temp.first] != -1){
						q.push({adj[temp.first][0][i], temp.second});
						visited[adj[temp.first][0][i]] = temp.second;
					}
				}
				for (int i = 0; i < (int)adj[temp.first][1].size(); ++i){
					if (visited[temp.first] != -1){
						q.push({adj[temp.first][1][i], temp.second ^ 1});
						visited[adj[temp.first][1][i]] = temp.second ^ 1;
					}
				}
				}
			visited.shrink_to_fit();
			while (!q.empty())q.pop();
			if (visited[b] == -1)cout << "?\n";
			else if (visited[b] == 0)cout << "R\n";
			else cout << "A\n";
		}
	}
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 796 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 972 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 983 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Execution timed out 1108 ms 257724 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Runtime error 796 ms 262148 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -