結果

問題 No.1641 Tree Xor Query
ユーザー roarisroaris
提出日時 2021-08-06 21:51:58
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 213 ms / 5,000 ms
コード長 1,098 bytes
コンパイル時間 4,151 ms
コンパイル使用メモリ 265,256 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2023-10-17 03:12:10
合計ジャッジ時間 5,961 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,128 KB
testcase_01 AC 3 ms
6,132 KB
testcase_02 AC 3 ms
6,128 KB
testcase_03 AC 3 ms
6,136 KB
testcase_04 AC 3 ms
6,140 KB
testcase_05 AC 3 ms
6,140 KB
testcase_06 AC 3 ms
6,140 KB
testcase_07 AC 3 ms
6,140 KB
testcase_08 AC 3 ms
6,132 KB
testcase_09 AC 3 ms
6,136 KB
testcase_10 AC 3 ms
6,136 KB
testcase_11 AC 3 ms
6,136 KB
testcase_12 AC 3 ms
6,136 KB
testcase_13 AC 212 ms
18,048 KB
testcase_14 AC 213 ms
18,048 KB
testcase_15 AC 5 ms
6,388 KB
testcase_16 AC 12 ms
6,652 KB
testcase_17 AC 10 ms
6,480 KB
testcase_18 AC 7 ms
6,624 KB
testcase_19 AC 8 ms
6,192 KB
testcase_20 AC 129 ms
12,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
typedef long long ll;

int N, Q;
int C[100010];
vector<int> G[100010];
vector<int> tour;
int s[100010];
int t[100010];
int c = 0;

void euler(int v, int pv) {
    s[v] = c++;
    tour.pb(v);
    for (int nv:G[v]) {
        if (nv==pv) continue;
        euler(nv, v);
    }
    t[v] = c;
}

int op(int x, int y) { return x^y;}
int e() {return 0;}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    cin >> N >> Q;
    rep(i, N) cin >> C[i];
    rep(i, N-1) {
        int a, b; cin >> a >> b;
        G[a-1].pb(b-1);
        G[b-1].pb(a-1);
    }
    euler(0, -1);
    
    segtree<int, op, e> st(N);
    rep(i, N) st.set(i, C[tour[i]]);
    
    int idx[N];
    rep(i, N) idx[tour[i]] = i;
    
    while (Q--) {
        int T, x, y; cin >> T >> x >> y;
        if (T==1) {
            st.set(idx[x-1], C[x-1]^y);
            C[x-1] ^= y;
        } else {
            cout << st.prod(s[x-1], t[x-1]) << endl;
        }
    }
}
0