結果

問題 No.1030 だんしんぐぱーりない
ユーザー SSRSSSRS
提出日時 2020-04-18 00:00:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,254 bytes
コンパイル時間 1,764 ms
コンパイル使用メモリ 179,088 KB
実行使用メモリ 21,628 KB
最終ジャッジ日時 2024-10-03 16:24:20
合計ジャッジ時間 11,232 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 234 ms
12,544 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 162 ms
6,816 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
6,816 KB
testcase_41 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int INF = 2000000000;
vector<vector<int>> child(vector<vector<int>> E, int r){
	int N = E.size();
	vector<vector<int>> c(N);
	queue<int> Q;
	Q.push(r);
	while (!Q.empty()){
		int v = Q.front();
		Q.pop();
		for (int w : E[v]){
			if (c[w].empty()){
				c[v].push_back(w);
				Q.push(w);
			}
		}
	}
	return c;
}
void dfs_c(vector<int> &C, vector<vector<int>> &c, int v){
  for (int w : c[v]){
    C[w] = max(C[v], C[w]);
    dfs_c(C, c, w);
  }
}
void dfs2(vector<int> &ET, vector<int> &pos, vector<vector<int>> &c, int v){
  pos[v] = ET.size();
  ET.push_back(v);
  for (int w : c[v]){
    dfs2(ET, pos, c, w);
    ET.push_back(v);
  }
}
vector<int> segtree_min(vector<int> &A){
	int N = 1;
	while (N < A.size()){
		N = N * 2;
	}
	vector<int> ST(N * 2 - 1);
	for (int i = 0; i < A.size(); i++){
		ST[i + N - 1] = A[i];
	}
	for (int i = A.size() + N - 1; i < N * 2 - 1; i++){
		ST[i] = INF;
	}
	for (int i = N - 2; i >= 0; i--){
		ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
	}
	return ST;
}
void segtree_min_update(vector<int> &ST, int i, int x){
	int N = (ST.size() + 1) / 2;
	i = i + N - 1;
	ST[i] = x;
	while (i > 0){
		i = (i - 1) / 2;
		ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
	}
	return;
}
int segtree_min_query(vector<int> &ST, int x, int y, int i, int L, int R){
	if (y <= L || R <= x){
		return INF;
	} else if (x <= L && R <= y){
		return ST[i];
	} else {
		int M = (L + R) / 2;
		int A = segtree_min_query(ST, x, y, i * 2 + 1, L, M);
		int B = segtree_min_query(ST, x, y, i * 2 + 2, M, R);
		return min(A, B);
	}
}
vector<int> segtree_max(vector<int> &A){
	int N = 1;
	while (N < A.size()){
		N = N * 2;
	}
	vector<int> ST(N * 2 - 1);
	for (int i = 0; i < A.size(); i++){
		ST[i + N - 1] = A[i];
	}
	for (int i = A.size() + N - 1; i < N * 2 - 1; i++){
		ST[i] = 0;
	}
	for (int i = N - 2; i >= 0; i--){
		ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
	}
	return ST;
}
void segtree_max_update(vector<int> &ST, int i, int x){
	int N = (ST.size() + 1) / 2;
	i = i + N - 1;
	ST[i] = x;
	while (i > 0){
		i = (i - 1) / 2;
		ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
	}
	return;
}
int segtree_max_query(vector<int> &ST, int x, int y, int i, int L, int R){
	if (y <= L || R <= x){
		return 0;
	} else if (x <= L && R <= y){
		return ST[i];
	} else {
		int M = (L + R) / 2;
		int A = segtree_max_query(ST, x, y, i * 2 + 1, L, M);
		int B = segtree_max_query(ST, x, y, i * 2 + 2, M, R);
		return max(A, B);
	}
}
int main(){
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> C(N);
  for (int i = 0; i < N; i++){
    cin >> C[i];
  }
  vector<int> A(K);
  for (int i = 0; i < K; i++){
    cin >> A[i];
    A[i]--;
  }
  vector<vector<int>> E(N);
  for (int i = 0; i < N - 1; i++){
    int e, f;
    cin >> e >> f;
    e--;
    f--;
    E[e].push_back(f);
    E[f].push_back(e);
  }
  vector<vector<int>> c = child(E, 0);
  dfs_c(C, c, 0);
  vector<int> ET;
  vector<int> pos(N);
  dfs2(ET, pos, c, 0);
  /*
  for (int i : ET){
    cout << i << ' ';
  }
  cout << endl;
  for (int i = 0; i < N; i++){
    cout << pos[i] << ' ';
  }
  cout << endl;
  */
  for (int i = 0; i < K; i++){
    A[i] = pos[A[i]];
    //cout << A[i] << ' ';
  }
  //cout << endl;
  vector<int> ST1 = segtree_min(ET);
  int x = (ST1.size() + 1) / 2;
  vector<int> ST2 = segtree_min(A);
  vector<int> ST3 = segtree_max(A);
  int y = (ST2.size() + 1) / 2;
  for (int i = 0; i < Q; i++){
    int T;
    cin >> T;
    if (T == 1){
      int X, Y;
      cin >> X >> Y;
      X--;
      Y--;
      segtree_min_update(ST2, X, pos[Y]);
      segtree_max_update(ST3, X, pos[Y]);
      /*
      for (int j = 0; j < K; j++){
        cout << A[j] << ' ';
      }
      cout << endl;
      */
    }
    if (T == 2){
      int L, R;
      cin >> L >> R;
      L--;
      int left = segtree_min_query(ST2, L, R, 0, 0, y);
      int right = segtree_max_query(ST3, L, R, 0, 0, y);
      //cout << "left = " << left << ", right = " << right << endl;
      cout << C[segtree_min_query(ST1, left, right + 1, 0, 0, x)] << endl;
    }
    /*
    cout << "ST2" << endl;
    for (int j : ST2){
        cout << j << ' ';
    } 
    cout << endl;
    cout << "ST3" << endl;
    for (int j : ST2){
        cout << j << ' ';
    }
    cout << endl;
    */
  }
}
0