#525014 (C++17) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	define
提出日時	2020-08-05 20:30:51
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	4,280 bytes
コンパイル時間	2,557 ms
コンパイル使用メモリ	217,112 KB
実行使用メモリ	35,884 KB
最終ジャッジ日時	2024-04-23 17:46:36
合計ジャッジ時間	12,043 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	132 ms 31,704 KB
testcase_08	AC	106 ms 14,636 KB
testcase_09	AC	174 ms 24,696 KB
testcase_10	AC	253 ms 23,636 KB
testcase_11	AC	166 ms 9,612 KB
testcase_12	AC	117 ms 6,944 KB
testcase_13	AC	93 ms 15,952 KB
testcase_14	AC	223 ms 16,116 KB
testcase_15	AC	174 ms 9,440 KB
testcase_16	AC	257 ms 27,076 KB
testcase_17	AC	266 ms 27,692 KB
testcase_18	AC	114 ms 11,000 KB
testcase_19	AC	242 ms 24,176 KB
testcase_20	AC	56 ms 9,560 KB
testcase_21	AC	172 ms 6,944 KB
testcase_22	AC	20 ms 6,940 KB
testcase_23	AC	246 ms 17,292 KB
testcase_24	AC	180 ms 16,980 KB
testcase_25	AC	108 ms 13,212 KB
testcase_26	AC	190 ms 13,604 KB
testcase_27	AC	230 ms 25,304 KB
testcase_28	AC	189 ms 14,444 KB
testcase_29	AC	135 ms 16,556 KB
testcase_30	AC	117 ms 18,628 KB
testcase_31	AC	116 ms 15,052 KB
testcase_32	AC	138 ms 6,940 KB
testcase_33	AC	87 ms 13,152 KB
testcase_34	AC	356 ms 28,908 KB
testcase_35	AC	356 ms 28,416 KB
testcase_36	AC	359 ms 28,404 KB
testcase_37	AC	343 ms 28,400 KB
testcase_38	AC	370 ms 28,168 KB
testcase_39	AC	357 ms 28,420 KB
testcase_40	WA	-
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function 'void HLD::make_path(int, int, 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;
      |                     ^~~~~

ソースコード

raw source code

#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";
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード