結果

問題 No.1197 モンスターショー
ユーザー 沙耶花沙耶花
提出日時 2020-08-22 17:47:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,348 ms / 3,000 ms
コード長 3,212 bytes
コンパイル時間 2,574 ms
コンパイル使用メモリ 211,440 KB
実行使用メモリ 52,876 KB
最終ジャッジ日時 2024-04-23 17:58:10
合計ジャッジ時間 29,449 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 212 ms
44,576 KB
testcase_08 AC 154 ms
19,700 KB
testcase_09 AC 518 ms
33,640 KB
testcase_10 AC 1,143 ms
32,588 KB
testcase_11 AC 460 ms
12,588 KB
testcase_12 AC 215 ms
8,192 KB
testcase_13 AC 206 ms
22,196 KB
testcase_14 AC 734 ms
22,552 KB
testcase_15 AC 434 ms
11,896 KB
testcase_16 AC 1,059 ms
38,952 KB
testcase_17 AC 1,014 ms
39,292 KB
testcase_18 AC 350 ms
14,456 KB
testcase_19 AC 975 ms
32,520 KB
testcase_20 AC 123 ms
12,208 KB
testcase_21 AC 388 ms
5,632 KB
testcase_22 AC 30 ms
5,504 KB
testcase_23 AC 941 ms
24,280 KB
testcase_24 AC 580 ms
24,188 KB
testcase_25 AC 238 ms
16,976 KB
testcase_26 AC 520 ms
17,784 KB
testcase_27 AC 666 ms
35,608 KB
testcase_28 AC 647 ms
19,764 KB
testcase_29 AC 338 ms
23,308 KB
testcase_30 AC 223 ms
26,700 KB
testcase_31 AC 329 ms
21,360 KB
testcase_32 AC 334 ms
5,376 KB
testcase_33 AC 181 ms
17,284 KB
testcase_34 AC 1,542 ms
41,264 KB
testcase_35 AC 1,534 ms
41,384 KB
testcase_36 AC 1,515 ms
41,264 KB
testcase_37 AC 1,500 ms
41,268 KB
testcase_38 AC 1,592 ms
41,528 KB
testcase_39 AC 1,524 ms
41,528 KB
testcase_40 AC 2,348 ms
52,876 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000005

vector<pair<int,int>> order;
vector<int> L;
int N,K,Q;
vector<int> dis;
vector<long long> calc;
vector<int> cnt;
vector<int> C;

template <typename T>
struct sparse_table{
	const T init_value = make_pair(1000000001,1000001);
	
	vector<T> v;
	int n;
	int sz;
	sparse_table(vector<T> &x){
		sz = x.size();
		for(int i=0;true;i++){
			if((1<<i)>sz){
				n = i;
				break;
			}
		}
		v.resize(sz*n,init_value);
		
		for(int i=0;i<sz;i++){
			v[i] = x[i];
		}
		
		for(int i=1;i<n;i++){
			for(int j=0;j<sz+1-(1<<i);j++){
				int temp = j+(1<<(i-1));
				v[i*sz+j] = func(v[(i-1)*sz+j],v[(i-1)*sz+temp]);
			}
		}
	}
	
	T query(int l,int r){
		int x = 31-__builtin_clz(r-l);
		return func(v[sz*x+l],v[sz*x+r-(1<<x)]);
	}
	
	T func(T a,T b){
		return min(a,b);
	}
};

void dfs(vector<vector<int>> &E,int now,int p){
	cnt[now] = C[now];
	for(int i=0;i<E[now].size();i++){
		dfs(E,E[now][i],now);
		cnt[now] += cnt[E[now][i]];
	}
}

void dfs2(vector<vector<int>> &E,int now,int p){
	if(p==-1){
		calc[now] = 0;
		for(int i=0;i<N;i++){
			calc[now] += (long long)dis[i] * C[i];
		}
	}
	else{
		calc[now] = calc[p];
		calc[now] -= cnt[now];
		calc[now] += K-cnt[now];
	}

	for(int i=0;i<E[now].size();i++){
		dfs2(E,E[now][i],now);
	}
}

void Erasedfs(vector<vector<int>> &E,int now,int p,int d=0){
	dis[now] =d;
	L[now] = order.size();
	order.emplace_back(d,now);
	vector<int> t;
	for(int i=0;i<E[now].size();i++){
		if(E[now][i]==p)continue;
		t.push_back(E[now][i]);
		Erasedfs(E,E[now][i],now,d+1);
		order.emplace_back(d,now);
	}
	E[now] = t;
	
}

int get_distance(sparse_table<pair<int,int>> &S,int u,int v){
	if(u==v)return 0;
	int l = min(L[u],L[v]);
	int r = max(L[u],L[v]);
	int x = S.query(l,r+1).second;
	return dis[u]+dis[v]-2*dis[x];
}
	

int main(){
	
	cin>>N>>K>>Q;
	C.resize(N,0);
	vector<int> pos(K);
	for(int i=0;i<K;i++){
		scanf("%d",&pos[i]);
		pos[i]--;
		C[pos[i]]++;
	}
	
	vector<vector<int>> E(N);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	dis.resize(N);
	L.resize(N);
	Erasedfs(E,0,-1);
	
	
	sparse_table<pair<int,int>> S(order);
	
	calc.resize(N);
	cnt.resize(N);
	dfs(E,0,-1);
	dfs2(E,0,-1);
	vector<pair<int,int>> Movement;
	for(int i=0;i<Q;i++){
		
		if(Movement.size()>350){
			for(int j=0;j<Movement.size();j++){
				C[pos[Movement[j].first]]--;
				pos[Movement[j].first] = Movement[j].second;
				C[pos[Movement[j].first]]++;
			}
			Movement.resize(0);
			dfs(E,0,-1);
			dfs2(E,0,-1);
		}
		
		int t;
		scanf("%d",&t);
		
		if(t==1){
			int p,d;
			scanf("%d %d",&p,&d);
			p--;d--;
			
			bool f = false;
			for(int j=0;j<Movement.size();j++){
				if(Movement[j].first==p){
					Movement[j].second = d;
					f=true;
					break;
				}
			}
			if(!f)Movement.emplace_back(p,d);
			
		}
		else{
			int e;
			scanf("%d",&e);
			e--;
			long long ans = calc[e];
			for(int j=0;j<Movement.size();j++){
				ans -= get_distance(S,e,pos[Movement[j].first]);
				ans += get_distance(S,e,Movement[j].second);
			}
			
			printf("%lld\n",ans);
			
		}
	}
	
	return 0;
}
0