結果

問題 No.1641 Tree Xor Query
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 2023-06-08 22:31:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 300 ms / 5,000 ms
コード長 2,967 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 115,804 KB
実行使用メモリ 23,192 KB
最終ジャッジ日時 2024-06-10 01:02:39
合計ジャッジ時間 3,767 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 299 ms
23,192 KB
testcase_14 AC 300 ms
23,016 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 16 ms
5,376 KB
testcase_17 AC 12 ms
5,376 KB
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 9 ms
5,376 KB
testcase_20 AC 210 ms
17,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <numeric>
#include <deque>
#include <complex>
#include <cassert>
 
using namespace std;
using ll = long long;
 
ll cnt=0;
vector<ll> in, out;
vector<ll> tour, C;

//in...頂点xに入ったのは何ステップ目か？
//out...頂点xから出たのは何ステップ目か？
//tour...i番目に訪れた頂点のxor(帰りは0)
void euler_tour(vector<vector<ll>> &E, ll from, ll p){
    tour.push_back(C[from]);
    in[from] = cnt;
    cnt++;
 
    for(auto to : E[from]){
        if (p == to) continue;
        euler_tour(E, to, from);
    }
 
    out[from] = cnt;
    tour.push_back(0);
    cnt++;
}

template<class S, S (*op)(S, S), S (*e)()>struct SegTree {
    vector<S> seg;
    long long N = 1;

    SegTree (long long n) : SegTree(vector<S>(n, e())) {}
    SegTree (const vector<S> &v){
        long long n = v.size();
        while (N < n) N *= 2;
        seg.resize(N*2-1, e());
        for (long long i=0; i<n; i++) seg[i+N-1] = v[i];
        for (long long i=N-2; i>=0; i--){
            seg[i] = op(seg[i*2+1], seg[i*2+2]);
        }
    }

    void set(long long loc, S val){
        loc += N-1;
        seg[loc] = val;
        while (loc != 0){
            loc = (loc-1)/2;
            seg[loc] = op(seg[loc*2+1], seg[loc*2+2]);
        }
    }

    //op(a[l], ..., a[r])
    S prod (long long l, long long r) const{
        return _prod(l, r, 0, 0, N-1);
    }

    S all_prod() const{
        return seg[0];
    }

    S _prod (long long l, long long r, long long idx, long long bitl, long long bitr) const{
        if (r < bitl || l > bitr) return e();
        if (l <= bitl && bitr <= r) return seg[idx];

        long long bitm = (bitl+bitr)/2;
        return op(_prod(l, r, idx*2+1, bitl, bitm), _prod(l, r, idx*2+2, bitm+1, bitr));
    }

    S get (long long i) const{
        return seg[i+N-1];
    }

    void show() const{
        for (int i=N-1; i<N*2-1; i++) cout << seg[i] << " ";
        cout << endl;
    }
};

long long op(long long a, long long b){
    return a ^ b;
}

long long e(){
    return 0;
}

int main(){
 
    ll N, Q, a, b, t;
    cin >> N >> Q;
    C.resize(N);
    for (int i=0; i<N; i++) cin >> C[i];
    vector<vector<ll>> E(N);
    for (int i=0; i<N-1; i++){
        cin >> a >> b; a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
 
    in.resize(N);
    out.resize(N);
 
    euler_tour(E, 0, -1);
    /*
    for (int i=0; i<N; i++) cout << in[i] << " ";
    cout << endl;
    for (int i=0; i<N; i++) cout << out[i] << " ";
    cout << endl;
    for (auto x : tour) cout << x << " ";
    cout << endl;
    */
    SegTree<ll, op, e> tree(tour);
 
    while(Q){
        Q--;
        cin >> t >> a >> b; a--;
        if (t == 1) tree.set(in[a], tree.get(in[a]) ^ b);
        else cout << tree.prod(in[a], out[a]) << endl;
    }
 
    return 0;
}
0