結果

問題 No.1197 モンスターショー
ユーザー definedefine
提出日時 2020-08-05 20:35:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 477 ms / 3,000 ms
コード長 4,276 bytes
コンパイル時間 2,915 ms
コンパイル使用メモリ 217,440 KB
実行使用メモリ 43,228 KB
最終ジャッジ日時 2024-04-23 17:47:21
合計ジャッジ時間 13,953 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 164 ms
37,676 KB
testcase_08 AC 130 ms
16,836 KB
testcase_09 AC 222 ms
27,808 KB
testcase_10 AC 322 ms
27,212 KB
testcase_11 AC 188 ms
11,012 KB
testcase_12 AC 127 ms
7,584 KB
testcase_13 AC 112 ms
18,392 KB
testcase_14 AC 275 ms
19,076 KB
testcase_15 AC 207 ms
10,612 KB
testcase_16 AC 338 ms
30,988 KB
testcase_17 AC 367 ms
31,160 KB
testcase_18 AC 140 ms
12,448 KB
testcase_19 AC 324 ms
27,340 KB
testcase_20 AC 68 ms
10,740 KB
testcase_21 AC 204 ms
5,632 KB
testcase_22 AC 23 ms
5,376 KB
testcase_23 AC 318 ms
20,296 KB
testcase_24 AC 241 ms
19,872 KB
testcase_25 AC 146 ms
15,236 KB
testcase_26 AC 243 ms
15,964 KB
testcase_27 AC 308 ms
29,452 KB
testcase_28 AC 236 ms
17,004 KB
testcase_29 AC 171 ms
19,652 KB
testcase_30 AC 148 ms
21,888 KB
testcase_31 AC 151 ms
17,536 KB
testcase_32 AC 157 ms
5,376 KB
testcase_33 AC 93 ms
15,096 KB
testcase_34 AC 473 ms
32,696 KB
testcase_35 AC 466 ms
32,708 KB
testcase_36 AC 469 ms
32,704 KB
testcase_37 AC 461 ms
32,696 KB
testcase_38 AC 466 ms
32,864 KB
testcase_39 AC 477 ms
32,744 KB
testcase_40 AC 469 ms
43,228 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void HLD::make_path(long long int, long long int, long long int)':
main.cpp:106:25: warning: 'mxidx' may be used uninitialized [-Wmaybe-uninitialized]
  106 |                         if(mxidx==i){
      |                         ^~
main.cpp:99:21: note: 'mxidx' was declared here
   99 |                 int mxidx,mx=0;
      |                     ^~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;
template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
struct HLD{
	using V=vector<pair<int,P>>;
	struct heavy_set{
		vector<int>ele;
		int depth,par,cost1=0,cost2=0;
		heavy_set(int v,int d,int par)
		:ele(1,v),depth(d),par(par){}
	};
	vector<vector<int>>G;
	vector<heavy_set>S;
	vector<int>subsize,stidx,eleidx;
	int subtree(int v,int p){
		int &sz=subsize[v];
		if(sz)return sz;
		sz=1;
		for(int i:G[v])if(i!=p)sz+=subtree(i,v);
		return sz;
	}
	void make_path(int v,int p,int id){
		stidx[v]=id;
		eleidx[v]=S[id].ele.size()-1;
		int mxidx,mx=0;
		for(int i:G[v])if(i!=p){
			if(mx<subtree(i,v)){
				mx=subtree(i,v);mxidx=i;
			}
		}
		for(int i:G[v])if(i!=p){
			if(mxidx==i){
				S[id].ele.push_back(i);
				make_path(i,v,id);
			}else {
				S.emplace_back(i,S[id].depth+1,v);
				make_path(i,v,S.size()-1);
			}
		}
	}
	int st(int v){return stidx[v];}
	int el(int v){return eleidx[v];}
	HLD(vector<vector<int>>&G):G(G){
		int N=G.size();
		subsize.resize(N);
		eleidx.resize(N);
		stidx.resize(N);
		S.emplace_back(0,0,0);
		make_path(0,0,0);
	}
};
int N,K,Q;
int C[100005],par[100005],cnt[100005],dis[100005];
vector<vector<int>>G;
void dfs(int x,int p){
	if(p)par[x]=par[p];
	else par[x]=x;
	for(int i:G[x])if(i!=p){
		dis[i]=dis[x]+1;
		dfs(i,x);
	}
}
signed main(){
	cin>>N>>K>>Q;G.resize(N);
	rep(i,K){cin>>C[i];C[i]--;}
	rep(i,N-1){
		int a,b;cin>>a>>b;a--;b--;
		G[a].push_back(b);G[b].push_back(a);
	}
	dfs(0,0);
	HLD hld(G);
	auto f=[](int a,int b){return a+b;};
	auto g=[](int a,int b,int sz){return a+b*sz;};
	auto h=[](int a,int b){return a+b;};
	vector<Segtree<int,int,decltype(f),decltype(g),decltype(h)>>segtrees;
	rep(i,len(hld.S))segtrees.emplace_back(len(hld.S[i].ele),f,g,h,0,0);
	auto add=[&](int a,int x){
		while(hld.st(a)!=0){
			segtrees[hld.st(a)].update(0,hld.el(a),x);
			hld.S[hld.st(a)].cost1+=x;
			a=hld.S[hld.st(a)].par;
		}
		segtrees[0].update(0,hld.el(a),x);
	};
	auto query=[&](int a){
		int res=0;
		while(hld.st(a)!=0){
			res+=segtrees[hld.st(a)].query(0,hld.el(a));
			res+=hld.S[hld.st(a)].cost1;
			a=hld.S[hld.st(a)].par;
		}
		return res+segtrees[0].query(0,hld.el(a));
	};
	int ans=0;
	rep(i,K){
		add(C[i],1);
		cnt[par[C[i]]]++;
		ans+=dis[C[i]];
	}
	for(auto i:segtrees)i.init();
	while(Q--){
		int type;cin>>type;
		if(type==1){
			int p,d;cin>>p>>d;p--;d--;
			add(C[p],-1);add(d,1);
			ans-=dis[C[p]];ans+=dis[d];
			cnt[par[C[p]]]--;cnt[par[d]]++;
			C[p]=d;
		}else {
			int e;cin>>e;e--;
			int res=ans;
			res-=query(e)*2;
			res+=dis[e]*K;
			cout<<res<<"\n";
		}
	}
}
0