#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 200002
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,L,loc[N],sz[N],fa[N],h[N];
vector<int>g[N];
struct BIT_2D{
vector<int>bit[44];
int n=0,m=42;
void init(int _n){
n=_n;
for (int i=0;i<=m;i++)
bit[i].resize(n+2,1);
}
void modify(int x,int y,int c){
x=m-x;
// cout<<"modify : "<<x<<' '<<y<<" "<<c<<'\n';
while (x<=m){
int ty=y;
while (ty<=n){
bit[x][ty]=(long long)(bit[x][ty])*(long long)c%(long long)L;
ty+=ty&(-ty);
}
x+=x&(-x);
}
}
long long query(int x,int y){
long long ans=1;
x=m-x;
// cout<<"query : "<<x<<' '<<y<<'\n';
while (x>0){
int ty=y;
while (ty>0){
ans=ans*(long long)(bit[x][ty])%L;
ty-=ty&(-ty);
}
x-=x&(-x);
}
return ans;
}
}cntl[N],cntr[N];
void dfs(int p,int lp){
fa[p]=lp;
for (auto i:g[p]){
if (i!=lp){
dfs(i,p);
sz[p]++;
loc[i]=sz[p];
}
}
}
signed main(){
fast
cin>>n>>L;
for (int i=1;i<n;i++){
int a,b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i=1;i<=n;i++)
cin>>h[i];
dfs(1,0);
loc[1]=1; sz[0]=1;
for (int i=0;i<=n;i++){
sz[i]++;
cntl[i].init(sz[i]);
cntr[i].init(sz[i]);
}
int q; cin>>q;
while (q--){
int type,x,d,w; cin>>type;
if (type==1){
cin>>x>>d>>w;
cntl[x].modify(d,1,w);
for (int i=0;i<d;i++){
if (x==0) break;
int pos=loc[x];
// cout<<x<<" "<<fa[x]<<' '<<pos<<" "<<d-i+1<<'\n';
cntl[fa[x]].modify(d-i-1,pos+1,w);
cntr[fa[x]].modify(d-i-1,sz[fa[x]]-pos+1,w);
// cout<<"dis : "<<d-i+1<<" OK\n";
x=fa[x];
}
}
else {
cin>>x;
long long ans=h[x];
long long tans1=cntl[x].query(0,sz[x]),tans2;
ans=(ans*tans1)%L;
// cout<<" -> "<<tans1<<'\n';
for (int i=1;i<20;i++){
if (x==0) break;
int pos=loc[x];
tans1=cntl[fa[x]].query(i,pos);
tans2=cntr[fa[x]].query(i,sz[fa[x]]-pos);
// cout<<" -> "<<tans1<<' '<<tans2<<'\n';
ans=(ans*tans1%L*tans2)%L;
x=fa[x];
}
cout<<ans<<'\n';
}
}
}
Compilation message
sprinkler.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
| ^
sprinkler.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:21:21: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
21 | void init(int _n){
| ^
sprinkler.cpp:21:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
26 | void modify(int x,int y,int c){
| ^
sprinkler.cpp:26:34: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
38 | long long query(int x,int y){
| ^
sprinkler.cpp:38:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
53 | void dfs(int p,int lp){
| ^
sprinkler.cpp:53:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
63 | signed main(){
| ^
sprinkler.cpp:63:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
421480 KB |
Output is correct |
| 2 |
Correct |
224 ms |
421480 KB |
Output is correct |
| 3 |
Correct |
218 ms |
421464 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
424228 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
421484 KB |
Output is correct |
| 2 |
Correct |
3875 ms |
978924 KB |
Output is correct |
| 3 |
Correct |
1902 ms |
976344 KB |
Output is correct |
| 4 |
Correct |
2939 ms |
976956 KB |
Output is correct |
| 5 |
Correct |
2811 ms |
977992 KB |
Output is correct |
| 6 |
Correct |
2092 ms |
990896 KB |
Output is correct |
| 7 |
Correct |
1918 ms |
1001112 KB |
Output is correct |
| 8 |
Correct |
1603 ms |
1041832 KB |
Output is correct |
| 9 |
Execution timed out |
4077 ms |
981816 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
421484 KB |
Output is correct |
| 2 |
Correct |
3875 ms |
978924 KB |
Output is correct |
| 3 |
Correct |
1902 ms |
976344 KB |
Output is correct |
| 4 |
Correct |
2939 ms |
976956 KB |
Output is correct |
| 5 |
Correct |
2811 ms |
977992 KB |
Output is correct |
| 6 |
Correct |
2092 ms |
990896 KB |
Output is correct |
| 7 |
Correct |
1918 ms |
1001112 KB |
Output is correct |
| 8 |
Correct |
1603 ms |
1041832 KB |
Output is correct |
| 9 |
Execution timed out |
4077 ms |
981816 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
421488 KB |
Output is correct |
| 2 |
Execution timed out |
4101 ms |
978084 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
244 ms |
421388 KB |
Output is correct |
| 2 |
Execution timed out |
4130 ms |
978828 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
421480 KB |
Output is correct |
| 2 |
Correct |
224 ms |
421480 KB |
Output is correct |
| 3 |
Correct |
218 ms |
421464 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
424228 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
