結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー zhichengzhicheng
提出日時 2024-10-16 09:57:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 876 ms / 10,000 ms
コード長 3,322 bytes
コンパイル時間 2,058 ms
コンパイル使用メモリ 170,144 KB
実行使用メモリ 52,864 KB
最終ジャッジ日時 2024-10-16 09:57:52
合計ジャッジ時間 28,170 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
40,960 KB
testcase_01 AC 27 ms
41,088 KB
testcase_02 AC 38 ms
41,344 KB
testcase_03 AC 38 ms
41,344 KB
testcase_04 AC 39 ms
41,344 KB
testcase_05 AC 37 ms
41,472 KB
testcase_06 AC 38 ms
41,344 KB
testcase_07 AC 831 ms
47,104 KB
testcase_08 AC 794 ms
47,232 KB
testcase_09 AC 850 ms
47,232 KB
testcase_10 AC 868 ms
47,360 KB
testcase_11 AC 818 ms
47,232 KB
testcase_12 AC 838 ms
47,104 KB
testcase_13 AC 842 ms
47,232 KB
testcase_14 AC 834 ms
47,232 KB
testcase_15 AC 856 ms
47,232 KB
testcase_16 AC 810 ms
47,232 KB
testcase_17 AC 787 ms
51,072 KB
testcase_18 AC 778 ms
52,864 KB
testcase_19 AC 742 ms
50,944 KB
testcase_20 AC 813 ms
52,096 KB
testcase_21 AC 775 ms
52,736 KB
testcase_22 AC 500 ms
46,848 KB
testcase_23 AC 499 ms
46,848 KB
testcase_24 AC 484 ms
46,848 KB
testcase_25 AC 853 ms
47,360 KB
testcase_26 AC 872 ms
47,360 KB
testcase_27 AC 844 ms
47,360 KB
testcase_28 AC 828 ms
47,360 KB
testcase_29 AC 876 ms
47,488 KB
testcase_30 AC 476 ms
47,232 KB
testcase_31 AC 479 ms
47,104 KB
testcase_32 AC 515 ms
47,232 KB
testcase_33 AC 676 ms
47,232 KB
testcase_34 AC 630 ms
47,232 KB
testcase_35 AC 669 ms
47,232 KB
testcase_36 AC 763 ms
47,104 KB
testcase_37 AC 624 ms
47,232 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'tag tag::operator+(tag)':
main.cpp:12:34: warning: narrowing conversion of '(((1 * ((long long int)((tag*)this)->tag::k)) * ((long long int)d.tag::k)) % ((long long int)((int)mod)))' from 'long long int' to 'int' [-Wnarrowing]
   12 |                 return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
      |                         ~~~~~~~~~^~~~
main.cpp:12:54: warning: narrowing conversion of '((((1 * ((long long int)((tag*)this)->tag::b)) * ((long long int)d.tag::k)) + ((long long int)d.tag::b)) % ((long long int)((int)mod)))' from 'long long int' to 'int' [-Wnarrowing]
   12 |                 return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
      |                                       ~~~~~~~~~~~~~~~^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=100010,mod=998244353;
int n,d[N],cnt,tot,first[N],nnext[N<<1],to[N<<1],dep[N],f[N],siz[N],son[N],top[N],seg[N],rev[N],pdep[N<<2];
struct tag{
	int k,b;
	tag(int _k=1,int _b=0){
		k=_k;
		b=_b;
	}
	tag operator+(tag d){
		return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
	}
	void operator+=(tag d){
		*this=*this+d;
	}
	bool operator!=(tag d){
		return k!=d.k||b!=d.b;
	}
}p[N<<2][12];
void add(int x,int y){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
}
void dfs1(int u,int fa){
	f[u]=fa;
	dep[u]=dep[fa]+1;
	siz[u]=1;
	for(int e=first[u];e;e=nnext[e]){
		if(to[e]!=fa){
			dfs1(to[e],u);
			siz[u]+=siz[to[e]];
			if(siz[to[e]]>siz[son[u]]){
				son[u]=to[e];
			}
		}
	}
}
void dfs2(int u){
	if(son[u]){
		top[son[u]]=top[u];
		seg[son[u]]=++cnt;
		rev[cnt]=son[u];
		dfs2(son[u]);
	}
	for(int e=first[u];e;e=nnext[e]){
		if(!top[to[e]]){
			seg[to[e]]=++cnt;
			top[to[e]]=rev[cnt]=to[e];
			dfs2(to[e]);
		}
	}
}
void build(int l,int r,int rt){
	int mid=(l+r)>>1;
	if(l==r){
		p[rt][0]={0,d[rev[l]]};
		pdep[rt]=dep[rev[l]];
		return;
	}
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pdep[rt]=min(pdep[rt<<1],pdep[rt<<1|1]);
}
void laz(int rt,int pos,tag now){
	if(pos>=pdep[rt]){
		p[rt][pos-pdep[rt]]+=now;
	}
}
void pushdown(int rt){
	for(int i=0;i<=10;i++){
		if(p[rt][i]!=(tag){1,0}){
			laz(rt<<1,i+pdep[rt],p[rt][i]);
			laz(rt<<1|1,i+pdep[rt],p[rt][i]);
			p[rt][i]={1,0};
		}
	}
	if(p[rt][11]!=(tag){1,0}){
		for(int i=0;i<=11;i++){
			if(i+pdep[rt<<1]-pdep[rt]>10){
				p[rt<<1][i]+=p[rt][11];
			}
			if(i+pdep[rt<<1|1]-pdep[rt]>10){
				p[rt<<1|1][i]+=p[rt][11];
			}
		}
		p[rt][11]={1,0};
	}
}
void update(int x,int y,int pos,int k,int b,int l,int r,int rt){
	int mid=(l+r)>>1;
	if(x<=l&&y>=r){
		if(pos==-1){
			for(int i=0;i<=11;i++){
				p[rt][i]+={k,b};
			}
		}
		else{
			laz(rt,pos,{k,b});
		}
		return;
	}
	pushdown(rt);
	if(x<=mid){
		update(x,y,pos,k,b,l,mid,rt<<1);
	}
	if(y>=mid+1){
		update(x,y,pos,k,b,mid+1,r,rt<<1|1);
	}
}
int query(int x,int l,int r,int rt){
	int mid=(l+r)>>1;
	if(l==r){
		return p[rt][0].b;
	}
	pushdown(rt);
	return x<=mid?query(x,l,mid,rt<<1):query(x,mid+1,r,rt<<1|1);
}
void change(int x,int y,int k,int b){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		update(seg[top[x]],seg[x],-1,k,b,1,n,1);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	update(seg[x],seg[y],-1,k,b,1,n,1);
}
void modify(int x,int y,int k,int b){
	for(int i=0;i<=y;i++){
		update(seg[x],seg[x]+siz[x]-1,dep[x]+y-i,k,b,1,n,1);
		if(i!=y){
			update(seg[x],seg[x]+siz[x]-1,dep[x]+y-i-1,k,b,1,n,1);
		}
		x=f[x];
		if(!x){
			for(int j=i+2;j<=y;j++){
				update(seg[1],seg[1]+siz[1]-1,dep[1]+y-j,k,b,1,n,1);
			}
			break;
		}
	}
}
int main(){
	int q,a,b,op,x,y,k;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
	}
	dfs1(1,0);
	cnt=seg[1]=rev[1]=top[1]=1;
	dfs2(1);
	build(1,n,1);
	while(q--){
		scanf("%d%d",&op,&x);
		if(op==1){
			printf("%d\n",query(seg[x],1,n,1));
		}
		else if(op==2){
			scanf("%d%d%d",&y,&k,&b);
			modify(x,y,k,b);
		}
		else if(op==3){
			scanf("%d%d",&k,&b);
			update(seg[x],seg[x]+siz[x]-1,-1,k,b,1,n,1);
		}
		else{
			scanf("%d%d%d",&y,&k,&b);
			change(x,y,k,b);
		}
	}
}
0