結果

問題 No.1030 だんしんぐぱーりない
ユーザー 沙耶花
提出日時 2020-04-17 22:40:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 521 ms / 2,000 ms
コード長 3,478 bytes
コンパイル時間 2,954 ms
コンパイル使用メモリ 213,168 KB
最終ジャッジ日時 2025-01-09 20:25:56
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:169:10: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
  169 | void dfs(auto &E,int now,auto &C){
      |          ^~~~
main.cpp:169:26: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
  169 | void dfs(auto &E,int now,auto &C){
      |                          ^~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x)+modulo)%modulo)
#define Inf 1000000000000000
struct lca{
    
    vector<int> depth;//depth[i] 頂点iの深さ
    vector<vector<int>> parents;//parents[i][j] 頂点iから2^j個上の親
    
    int max_j = 30;
    
    lca(){
    }
    
    lca(int n,vector<vector<int>> &E){
        depth.assign(E.size(),-1);
        parents.assign(E.size(),vector<int>(max_j,-1));
        
        stack<int> s;
        s.push(n);
        depth[n] = 0;
        while(s.size()!=0){
            int k = s.top();
            s.pop();
            for(int i=0;i<E[k].size();i++){
                int x = E[k][i];
                if(depth[x]!=-1)continue;
                s.push(x);
                depth[x] = depth[k]+1;
                for(int j=0;j<max_j;j++){
                    if(j==0){
                        parents[x][j] = k;
                    }
                    else{
                        parents[x][j] = parents[parents[x][j-1]][j-1];
                    }
                    if(parents[x][j] == -1)break;
                }
            }
        }
    }
    
    //頂点uのk番目の親
    int kth_parent(int u,int k){
        for(int i=0;i<max_j;i++){
            if(k==0)break;
            if(u==-1)break;
            if(k%2){
                u = parents[u][i];
            }
            k/=2;
        }
        return u;
    }
    
    int query(int u,int v){
        if(depth[u]<depth[v])swap(u,v);
        u = kth_parent(u,depth[u]-depth[v]);
        
        if(u==v){
            return u;
        }
        
        for(int i=max_j-1;i>=0;i--){
            if(parents[u][i]!=parents[v][i]){
                u = parents[u][i];
                v = parents[v][i];
            }
        }
        
        return parents[u][0];
        
    }
    
    int get_distance(int u,int v){
        return depth[u]+depth[v]-2*depth[query(u,v)];
    }
    
    
};
template <typename T,typename F>
struct segtree{
    //元データx[i]はv[n+i]
    //v[i]の親はv[i/2],子はv[i*2]とv[i*2+1]
    F func;
    vector<T> v;
    int n;
    
    const T init_value = -1;
    
    segtree(int sz,F f):func(f){
        n=1;
        while(true){
            if(n>=sz)break;
            n*=2;
        }
        v.resize(2*n,init_value);
        for(int i=n-1;i>=0;i--){
            v[i]=func(v[i<<1],v[(i<<1)+1]);
        }
    }
    
    segtree(vector<T> &x,F f):func(f){
        n=1;
        while(true){
            if(n>=x.size())break;
            n*=2;
        }
        v.resize(2*n,init_value);
        
        for(int i=0;i<x.size();i++){
            v[n+i]=x[i];
        }
        for(int i=n-1;i>=0;i--){
            v[i]=func(v[i<<1],v[(i<<1)+1]);
        }
    }
    void update(int x,T val){
        x+=n;
        v[x]=val;
        while(x>0){
            x>>=1;
            v[x]=func(v[x<<1],v[(x<<1)+1]);
        }
    }
    
    //区間[l,r)におけるクエリ処理
    T query(int l,int r){
        if(l>=r)return init_value;
        l+=n;
        r+=n;
        T res1 = init_value;
        T res2 = init_value;
        while(true){
            if(l&1){
                res1=func(res1,v[l++]);
            }
            if(r&1){
                res2=func(v[--r],res2);
            }
            if(l>=r)break;
            l>>=1;r>>=1;
        }
        return func(res1,res2);
    }
    
    void show(){
        int n = 1;
        for(int i=1;i<v.size();i++){
            for(int j=0;j<n;j++){
                if(j!=0)cout<<' ';
                cout<<v[i+j];
            }
            cout<<endl;
            i+=n-1;
            n*=2;
        }
    }
    
};
lca L;
void dfs(auto &E,int now,auto &C){
    for(int i=0;i<E[now].size();i++){
        int to = E[now][i];
        C[to] = max(C[to],C[now]);
        dfs(E,to,C);
    }
}
int main() {
    
    int N,K,Q;
    cin>>N>>K>>Q;
    
    vector<int> C(N);
    vector<int> A(K);
    
    for(int i=0;i<N;i++)cin>>C[i];
    for(int i=0;i<K;i++){
        cin>>A[i];
        A[i]--;
    }
    
    vector<vector<int>> E(N,vector<int>());
    
    for(int i=0;i<N-1;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        E[v].push_back(u);
    }
    
    L = *(new lca(0,E));
    
    auto f = [](int a,int b){
        if(a==-1)return b;
        if(b==-1)return a;
        return L.query(a,b);
    };
    
    dfs(E,0,C);
    
    segtree<int,decltype(f)> seg(A,f);
    
    for(int i=0;i<Q;i++){
        int T,X,Y;
        cin>>T>>X>>Y;
        X--;Y--;
        if(T==1){
            seg.update(X,Y);
        }
        else{
            cout<<C[seg.query(X,Y+1)]<<endl;
        }
    }
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0