結果

問題 No.1197 モンスターショー
ユーザー definedefine
提出日時 2020-08-05 20:48:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 403 ms / 3,000 ms
コード長 4,554 bytes
コンパイル時間 3,238 ms
コンパイル使用メモリ 223,892 KB
実行使用メモリ 43,236 KB
最終ジャッジ日時 2024-10-15 18:25:29
合計ジャッジ時間 12,461 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 148 ms
37,420 KB
testcase_08 AC 117 ms
16,844 KB
testcase_09 AC 179 ms
27,684 KB
testcase_10 AC 275 ms
27,088 KB
testcase_11 AC 162 ms
11,020 KB
testcase_12 AC 110 ms
7,432 KB
testcase_13 AC 93 ms
18,268 KB
testcase_14 AC 230 ms
18,952 KB
testcase_15 AC 177 ms
10,608 KB
testcase_16 AC 281 ms
30,740 KB
testcase_17 AC 295 ms
31,032 KB
testcase_18 AC 123 ms
12,580 KB
testcase_19 AC 273 ms
27,112 KB
testcase_20 AC 60 ms
10,672 KB
testcase_21 AC 175 ms
5,504 KB
testcase_22 AC 20 ms
5,248 KB
testcase_23 AC 263 ms
20,032 KB
testcase_24 AC 191 ms
19,876 KB
testcase_25 AC 112 ms
15,244 KB
testcase_26 AC 195 ms
15,864 KB
testcase_27 AC 260 ms
29,328 KB
testcase_28 AC 204 ms
16,756 KB
testcase_29 AC 145 ms
19,396 KB
testcase_30 AC 126 ms
21,760 KB
testcase_31 AC 120 ms
17,412 KB
testcase_32 AC 139 ms
5,248 KB
testcase_33 AC 87 ms
15,104 KB
testcase_34 AC 403 ms
32,700 KB
testcase_35 AC 379 ms
32,792 KB
testcase_36 AC 386 ms
32,676 KB
testcase_37 AC 383 ms
32,824 KB
testcase_38 AC 380 ms
32,608 KB
testcase_39 AC 378 ms
32,744 KB
testcase_40 AC 389 ms
43,236 KB
testcase_41 AC 2 ms
5,248 KB
testcase_42 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void HLD::make_path(long long int, long long int, long long int)':
main.cpp:108:42: warning: 'mxidx' may be used uninitialized [-Wmaybe-uninitialized]
  108 |                                 make_path(i,v,id);
      |                                 ~~~~~~~~~^~~~~~~~
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);

	//Size Check
	assert(N<=1e5&&K<=1e5&&Q<=1e5);
	assert(N>=1&&K>=1&&Q>=1);

	rep(i,K){cin>>C[i];C[i]--;}
	rep(i,N-1){
		int a,b;cin>>a>>b;a--;b--;
		assert(0<=a&&0<=b&&a!=b);
		assert(a<N&&b<N);
		G[a].push_back(b);G[b].push_back(a);
	}
	dfs(0,0);

	//Connection Check
	REP(i,N)assert(dis[i]);

	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;

		//type check
		assert(type==1||type==2);

		if(type==1){
			int p,d;cin>>p>>d;p--;d--;

			assert(0<=p&&p<K&&0<=d&&d<N);

			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--;

			assert(0<=e&&e<N);
			
			int res=ans;
			res-=query(e)*2;
			res+=dis[e]*K;
			cout<<res<<"\n";
		}
	}
}
0