Submission #518341

#	Time	Username	Problem	Language	Result	Execution time	Memory
518341		thegrimbee	Experimental Charges (NOI19_charges)	C++14	7 / 100	627 ms	262148 KiB

charges

#include <bits/stdc++.h>
#define int long long
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 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 14
• Subtask 4: 0 / 12
• Subtask 5: 0 / 25
• Subtask 6: 0 / 31