Submission #425460

#	Time	Username	Problem	Language	Result	Execution time	Memory
425460		errorgorn	Experimental Charges (NOI19_charges)	C++17	100 / 100	41 ms	9744 KiB

charges

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii, int> iii;
vector<ii> al[100005];
vector<iii> s;
int charge[100005],p[100005],r[100005];
inline int read() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	  }
    return x;
}
void dfs(int i){
  for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
    if (charge[(*it).first]==-1){
      charge[(*it).first]=charge[i]^(*it).second;
      dfs((*it).first);
    }
  }
}
int parent(int i){
  return (p[i]==i ? i : p[i]=parent(p[i]));
}
bool same(int i,int j){
  return parent(i)==parent(j);
}
void unions(int i,int j){
  i=parent(i),j=parent(j);
  if (i==j) return;
  if (r[i]<r[j]) p[i]=j;
  else{
    p[j]=i;
    if (r[i]==r[j]) r[i]++;
  }
}
int main(){
  for (int x=0;x<100005;x++){
    p[x]=x;
    charge[x]=-1;
  }
  int n,q,a,b;
  char c;
  n=read(),q=read();
  while (q--){
    c=getchar();
    getchar();
    a=read(),b=read();
    if (c=='Q') s.push_back(iii (ii(a,b),0));
    else{
      s.push_back(iii (ii(a,b),1));
      al[a].push_back(ii (b,(c=='R')? 0:1));
      al[b].push_back(ii (a,(c=='R')? 0:1));
    }
  }
  for (int x=1;x<=n;x++){
    if (charge[x]==-1){
      charge[x]=0;
      dfs(x);
    }
  }
  for (vector<iii>::iterator it=s.begin();it!=s.end();it++){
    a=(*it).first.first,b=(*it).first.second,c=(*it).second;
    if ((*it).second==0){
      putchar_unlocked(same(a,b) ? ((charge[a]==charge[b])? 'R':'A'): '?');
      putchar_unlocked('\n');
    }
    else unions(a,b);
  }
}

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