제출 #1130888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130888		jackofall718	Experimental Charges (NOI19_charges)	C++20	100 / 100	32 ms	2444 KiB

charges

//NOI 2019 Prelims problem 3
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
#define vn vector <ll>
using namespace std;
const int MAX_N = 1e9 + 7;
#define pii pair <ll,ll>
const ll INF = 0x3f3f3f3f3f3f3f3f;

#define pb push_back  

#define srt(vp) sort(vp.begin(), vp.end()) 
pair <ll,bool> p[100010];

pair <ll,bool> fp(ll x){
  if (p[x].first==x) return make_pair(x,0);
  pair <ll,bool> root = fp(p[x].first); //here p[x].first is the parent of the node obtained from the merge function..we replace immediate parent with the final node
  return p[x]=make_pair(root.first , root.second ^ p[x].second);
}

void mg(ll x,ll y,bool charge){//merge nodes
 pair <ll,bool> root1=fp(x),root2 = fp(y);
 if (root1.first==root2.second)return;//same set already return
 p[root1.first]=make_pair(root2.first,root2.second ^ charge ^root1.second);//notice we dont join smaller set with bigger set or anything
}

int main() {
  ios::sync_with_stdio(false);        
  cin.tie(nullptr);
  ll n,q;
  cin>>n>>q;
  for (int i=1;i<=n;i++) p[i]=make_pair(i,0);
  for (int i=0;i<q;i++){
    char a;
    ll b,c;
    cin>>a>>b>>c;
    if (a=='Q'){
    pair <ll,bool> first1,second2;
    first1 = fp(b);
    second2 = fp(c);
    if (first1.first != second2.first) cout<<"?"<<endl;
    else{
      if (second2.second != first1.second){
        cout<<"A"<<endl;
      }
      else{
        cout<<"R"<<endl;
      }
    }

    }
    else{
      mg(b,c,a=='A');
    }
  }
   
}
//DSU is used..disjoint set union
//so basically in every set each nodes charge is stored relative to a root(if root is + and node repels it also is + example) and when we merge sets we change the root of the first set to the second set and the resulting charge of the p[firstroot] is the xor of its charge,rots charge and r
//1 means attract,0 means repel and 0(false) in p means it is same charge as root and 1 (true) means it is opposite charge of parent

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