結果

問題 No.1030 だんしんぐぱーりない
ユーザー carrot46carrot46
提出日時 2020-04-17 23:14:37
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 487 ms / 2,000 ms
コード長 3,635 bytes
コンパイル時間 1,960 ms
コンパイル使用メモリ 173,440 KB
実行使用メモリ 27,196 KB
最終ジャッジ日時 2024-04-14 15:31:33
合計ジャッジ時間 15,519 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
22,656 KB
testcase_01 AC 17 ms
22,656 KB
testcase_02 AC 17 ms
22,592 KB
testcase_03 AC 16 ms
22,528 KB
testcase_04 AC 17 ms
22,528 KB
testcase_05 AC 340 ms
25,404 KB
testcase_06 AC 283 ms
25,916 KB
testcase_07 AC 204 ms
24,504 KB
testcase_08 AC 202 ms
24,768 KB
testcase_09 AC 272 ms
25,916 KB
testcase_10 AC 159 ms
23,224 KB
testcase_11 AC 328 ms
25,660 KB
testcase_12 AC 320 ms
23,736 KB
testcase_13 AC 256 ms
24,760 KB
testcase_14 AC 373 ms
25,708 KB
testcase_15 AC 196 ms
24,380 KB
testcase_16 AC 331 ms
23,744 KB
testcase_17 AC 284 ms
25,024 KB
testcase_18 AC 406 ms
25,788 KB
testcase_19 AC 243 ms
23,228 KB
testcase_20 AC 273 ms
23,352 KB
testcase_21 AC 241 ms
25,400 KB
testcase_22 AC 261 ms
23,356 KB
testcase_23 AC 325 ms
24,124 KB
testcase_24 AC 261 ms
24,504 KB
testcase_25 AC 288 ms
24,892 KB
testcase_26 AC 216 ms
23,268 KB
testcase_27 AC 240 ms
23,740 KB
testcase_28 AC 356 ms
25,024 KB
testcase_29 AC 224 ms
23,868 KB
testcase_30 AC 240 ms
23,224 KB
testcase_31 AC 260 ms
23,480 KB
testcase_32 AC 308 ms
26,044 KB
testcase_33 AC 306 ms
25,408 KB
testcase_34 AC 158 ms
23,488 KB
testcase_35 AC 487 ms
27,068 KB
testcase_36 AC 474 ms
27,012 KB
testcase_37 AC 477 ms
27,196 KB
testcase_38 AC 482 ms
27,016 KB
testcase_39 AC 476 ms
27,080 KB
testcase_40 AC 17 ms
22,528 KB
testcase_41 AC 16 ms
22,536 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, -1), ran(1e+5 + 10);
mat G(1e+5 + 10, vec(0)), dbl(18, 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, 18) if((dif>>i)&1) q = dbl[i][q];
    if(p == q) return p;
    Rrep(i,18) {
        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 < K; ++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[t].push_back(s);
    }
    dfs(0, 0, 0, 0);
    reps(i,1,18){
        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(K + 10, -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