結果

問題 No.1030 だんしんぐぱーりない
ユーザー carrot46carrot46
提出日時 2020-04-17 23:00:25
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,658 bytes
コンパイル時間 1,884 ms
コンパイル使用メモリ 173,756 KB
実行使用メモリ 28,236 KB
最終ジャッジ日時 2024-04-14 15:20:55
合計ジャッジ時間 15,577 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
21,888 KB
testcase_01 AC 15 ms
21,760 KB
testcase_02 AC 15 ms
21,888 KB
testcase_03 AC 15 ms
21,888 KB
testcase_04 AC 15 ms
21,760 KB
testcase_05 AC 366 ms
27,448 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 RE -
testcase_09 AC 294 ms
27,264 KB
testcase_10 RE -
testcase_11 WA -
testcase_12 AC 341 ms
27,180 KB
testcase_13 AC 277 ms
26,028 KB
testcase_14 WA -
testcase_15 RE -
testcase_16 AC 364 ms
25,388 KB
testcase_17 AC 302 ms
27,784 KB
testcase_18 AC 422 ms
26,032 KB
testcase_19 AC 256 ms
22,828 KB
testcase_20 AC 291 ms
24,620 KB
testcase_21 AC 257 ms
25,512 KB
testcase_22 AC 283 ms
24,748 KB
testcase_23 AC 348 ms
24,240 KB
testcase_24 RE -
testcase_25 WA -
testcase_26 RE -
testcase_27 RE -
testcase_28 AC 378 ms
25,256 KB
testcase_29 AC 243 ms
26,796 KB
testcase_30 AC 254 ms
25,008 KB
testcase_31 AC 274 ms
24,364 KB
testcase_32 WA -
testcase_33 AC 320 ms
26,796 KB
testcase_34 WA -
testcase_35 AC 507 ms
28,048 KB
testcase_36 AC 496 ms
28,132 KB
testcase_37 AC 510 ms
28,148 KB
testcase_38 AC 510 ms
28,052 KB
testcase_39 AC 502 ms
28,236 KB
testcase_40 AC 16 ms
21,888 KB
testcase_41 AC 16 ms
21,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}

vec c(1e+5 + 10), a(1e+5 + 10), ran(1e+5 + 10);
mat G(1e+5 + 10, vec(0)), dbl(17, vec(1e+5 + 10, -1));
void dfs(int v, int p, ll pc, int r){
    dbl[0][v] = p;
    ran[v] = r;
    chmax(c[v], pc);
    for(int to : G[v]){
        if(to != p) dfs(to, v, c[v], r + 1);
    }
}

ll LCA(int p, int q){
    if(p == -1 || q == -1) return max(p, q);
    if(ran[p] > ran[q]) swap(p, q);
    int dif = ran[q] - ran[p];
    Rrep(i, 17) if((dif>>i)&1) q = dbl[i][q];
    if(p == q) return p;
    Rrep(i,17) {
        if(dbl[i][p] != dbl[i][q]){
            p = dbl[i][p];
            q = dbl[i][q];
        }
    }
    return dbl[0][p];
}

int main() {
    class SEGTREE{
                ll n, dflt;
          		vector<ll> dat;
            public:
            	SEGTREE(unsigned long _n, ll _a) : dat(_n * 4, _a){
            	    n = 1;
            	    dflt = _a;
            	    while(n < _n) n *= 2;
                }
                void update(ll k, ll a){
                    k += n;
                    dat[k] = a;
                    while(k > 0){
                        k /= 2;
                        dat[k] = LCA(dat[k * 2], dat[k * 2 + 1]);
                    }
                }
                void init(vector<ll> &v){
            	    for(int i = 0; i < v.size(); ++i) dat[i + n] = v[i];
            	    for(int i = n - 1; i >= 1; --i) {
            	        dat[i] = LCA(dat[i * 2], dat[i * 2 + 1]);
            	    }
            	}
                ll Q(ll a, ll b){
            	    return query(a, b, 1, 0, n);
            	}
                ll query(ll a, ll b, ll k, ll l, ll r){
                    if(r <= a || b <= l) return dflt;
                    if(a <= l && r <= b) return dat[k];
                    ll vl = query(a, b, k * 2, l, (l + r) / 2);
                    ll vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
                    return LCA(vl, vr);
                }
                //単項にアクセスする[]だが、書き換え厳禁
                //一応後でinitすれば書き換えてもよさそうだが…
                ll & operator [](int k) {return dat[k + n];}
        };
    cin>>N>>K>>Q;
    rep(i,N) cin>>c[i];
    rep(i,K){
        cin>>a[i];
        --a[i];
    }
    rep(i,N - 1){
        int s, t;
        cin>>s>>t;
        --s;
        --t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    dfs(0, 0, 0, 0);
    reps(i,1,17){
        rep(j,N){
            //if(dbl[i-1][j] < 0 || dbl[i-1][j] >= N) cout<<i<<' '<<j<<' '<<dbl[i-1][j]<<endl;
            dbl[i][j] = dbl[i-1][dbl[i-1][j]];
        }
    }
    //cout<<'a'<<endl;
    SEGTREE seg(N, -1);
    a.resize(K);
    seg.init(a);
    rep(i,Q){
        cin>>M;
        if(M == 1){
            int x, y;
            cin>>x>>y;
            --x;
            --y;
            seg.update(x, y);
        }else{
            int l, r;
            cin>>l>>r;
            cout<<c[seg.Q(l - 1, r)]<<endl;
        }
    }
}
0