제출 #524080

#제출 시각아이디문제언어결과실행 시간메모리
524080bebecanvasExperimental Charges (NOI19_charges)C++14
100 / 100
53 ms13372 KiB
#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);} } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...