結果

問題 No.1641 Tree Xor Query
ユーザー harurunharurun
提出日時 2021-06-21 01:18:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 956 ms
コンパイル使用メモリ 86,708 KB
実行使用メモリ 17,564 KB
最終ジャッジ日時 2024-09-17 00:52:16
合計ジャッジ時間 7,748 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

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