結果

問題 No.1030 だんしんぐぱーりない
ユーザー 沙耶花沙耶花
提出日時 2020-04-17 22:40:03
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 3,478 bytes
コンパイル時間 2,733 ms
コンパイル使用メモリ 217,296 KB
実行使用メモリ 39,552 KB
最終ジャッジ日時 2024-04-14 14:57:49
合計ジャッジ時間 14,777 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 329 ms
34,816 KB
testcase_06 AC 263 ms
26,240 KB
testcase_07 AC 175 ms
12,800 KB
testcase_08 AC 182 ms
16,000 KB
testcase_09 AC 276 ms
34,944 KB
testcase_10 AC 122 ms
7,552 KB
testcase_11 AC 284 ms
18,816 KB
testcase_12 AC 299 ms
32,256 KB
testcase_13 AC 248 ms
28,288 KB
testcase_14 AC 340 ms
27,136 KB
testcase_15 AC 148 ms
6,944 KB
testcase_16 AC 302 ms
24,320 KB
testcase_17 AC 287 ms
36,736 KB
testcase_18 AC 367 ms
28,416 KB
testcase_19 AC 209 ms
11,904 KB
testcase_20 AC 244 ms
20,352 KB
testcase_21 AC 228 ms
25,856 KB
testcase_22 AC 242 ms
21,376 KB
testcase_23 AC 288 ms
18,944 KB
testcase_24 AC 211 ms
9,216 KB
testcase_25 AC 252 ms
17,920 KB
testcase_26 AC 163 ms
6,940 KB
testcase_27 AC 182 ms
6,940 KB
testcase_28 AC 315 ms
24,576 KB
testcase_29 AC 229 ms
31,488 KB
testcase_30 AC 219 ms
22,144 KB
testcase_31 AC 230 ms
19,456 KB
testcase_32 AC 284 ms
26,368 KB
testcase_33 AC 295 ms
32,512 KB
testcase_34 AC 124 ms
8,832 KB
testcase_35 AC 453 ms
39,424 KB
testcase_36 AC 438 ms
39,468 KB
testcase_37 AC 447 ms
39,428 KB
testcase_38 AC 457 ms
39,424 KB
testcase_39 AC 459 ms
39,552 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0