結果

問題 No.1641 Tree Xor Query
ユーザー harurun
提出日時 2021-06-21 01:18:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 865 ms
コンパイル使用メモリ 84,876 KB
最終ジャッジ日時 2025-01-22 10:55:05
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <deque>
#include <stdio.h>
#include <vector>
using namespace std;
#define ll long long

const ll bit_length=10;

ostream& operator<<(ostream& os,vector<vector<ll>>& a){
  for(int i=0;i<(ll)a.size();i++){
    os<<i+1<<":";
    for(ll j:a.at(i)){
      os<<j+1<<" ";
    }
    os<<"\n";
  }
  return os;
}

int main(){
  ll N,Q,a,b,T,x,y,ans,q;
  cin>>N>>Q;
  vector<ll>C(N);
  for(int i=0;i<N;i++){
    cin>>C.at(i);
  }
  vector<vector<ll>>d(N);
  for(int i=0;i<N-1;i++){
    cin>>a>>b;
    d.at(a-1).push_back(b-1);
    d.at(b-1).push_back(a-1);
  }
  //cerr<<d<<endl;
  
  deque<ll>que;
  vector<bool>B(N,false);
  vector<ll>depth(N,0);
  que.push_back(0);
  while(!que.empty()){
    q=que.back();que.pop_back();
    B.at(q)=true;
    for(ll i:d.at(q)){
      if(B.at(i))continue;
      que.push_back(i);
      depth.at(i)+=depth.at(q)+1;
    }
  }

  deque<ll>dq;
  vector<bool>check(N,false);
  for(int i=0;i<Q;i++){
    cin>>T>>x>>y;
    x--;
    if(T==1){
      C.at(x)=C.at(x)^y;
    }else{
      dq.clear();
      ans=x;
      dq.push_back(x);
      fill(check.begin(),check.end(),false);
      while(!dq.empty()){
        q=dq.back();dq.pop_back();
        //cerr<<"now:"<<q+1<<endl;
        check.at(q)=true;
        ans^=C.at(q);
        for(ll j:d.at(q)){
          if(check.at(j))continue;
          if(depth.at(j)>depth.at(q))dq.push_back(j);
        }
      }
      printf("%lld\n",ans^x);
    }
  }
  return 0;
}
0