oj.uz

Submission #889068

# Submission time Handle Problem Language Result Execution time Memory
889068 2023-12-18T18:32:29 Z amirhoseinfar1385 Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 655048 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int q,high[maxn],n,mod,timea=0,part[maxn];
pair<int,int>stf[maxn];
struct segment{
	vector<long long>seg;
	vector<pair<pair<int,int>,int>>tof;
	int sz=0;
	void create(){
		while(__builtin_popcount(sz)!=1){
			sz++;
		}
		seg.resize(sz*2,1);
	}
	void add(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]*=w;
			seg[i]%=mod;
			return ;
		}
		int m=(l+r)>>1;
		add((i<<1),l,m,tl,tr,w);
		add((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	void adda(int tl,int tr,int w){
		tof.push_back(make_pair(make_pair(tl,tr),w));
	}
	void calc(){
		for(auto x:tof){
			add(1,0,sz-1,x.first.first,x.first.second,x.second);
		}
		tof.clear();
	}
	int pors(int i){
		if(i==0){
			return 1;
		}
		int ret=seg[i]*pors((i>>1))%mod;
		return ret;
	}
}seg[maxn];
vector<pair<int,int>>alll[maxn];
 
void pre(int u=1,int par=1){
	part[u]=par;
	timea++;
	stf[u].first=timea;
	alll[high[u]].push_back(make_pair(stf[u].first,u));
	for(auto x:adj[u]){
		if(x!=par){
			high[x]=high[u]+1;
			pre(x,u);
		}
	}
	stf[u].second=timea;
}
 
void upd(int u,int dis,int w){
	int z=0;
	int lev=high[u]+dis;
	while(lev>=0&&high[u]<=lev){
		if(lev<maxn){
			int l=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].first,-1))-alll[lev].begin();
			int r=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].second+1,-1))-alll[lev].begin();
			r--;
			seg[lev].adda(l,r,w);
		}
		if(z==1){
			u=part[u];
			lev--;
			z=0;
		}
		else{
			lev--;
			z=1;
		}
	}
}
 
void solve(int u){
	seg[high[u]].calc();
	int ind=lower_bound(alll[high[u]].begin(),alll[high[u]].end(),make_pair(stf[u].first,u))-alll[high[u]].begin();
	cout<<seg[high[u]].pors(ind+seg[high[u]].sz)<<"\n";
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>mod;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pre(1);
	for(int i=0;i<maxn;i++){
		seg[i].sz=alll[i].size();
		seg[i].create();
	}
	for(int i=1;i<=n;i++){
		int d;
		cin>>d;
		upd(i,0,d);
	}
	cin>>q;
	for(int i=0;i<q;i++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,d,w;
			cin>>u>>d>>w;
			if(d>40){
				assert(0);
			}
			upd(u,d,w); 
		}
		else{
			int u;
			cin>>u;
			solve(u);
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30040 KB Output is correct
2 Correct 14 ms 30040 KB Output is correct
3 Correct 15 ms 30044 KB Output is correct
4 Correct 19 ms 30616 KB Output is correct
5 Correct 18 ms 30300 KB Output is correct
6 Correct 18 ms 30300 KB Output is correct
7 Correct 17 ms 30296 KB Output is correct
8 Correct 17 ms 30300 KB Output is correct
9 Correct 15 ms 30044 KB Output is correct
10 Correct 15 ms 30044 KB Output is correct
11 Correct 17 ms 30076 KB Output is correct
12 Correct 15 ms 30044 KB Output is correct
13 Correct 15 ms 30044 KB Output is correct
14 Correct 15 ms 30124 KB Output is correct
15 Correct 15 ms 30044 KB Output is correct
16 Correct 15 ms 30188 KB Output is correct
17 Correct 15 ms 30044 KB Output is correct
18 Correct 15 ms 30044 KB Output is correct
19 Correct 14 ms 30208 KB Output is correct
20 Correct 15 ms 30044 KB Output is correct
21 Correct 15 ms 30044 KB Output is correct
22 Correct 15 ms 30044 KB Output is correct
23 Correct 16 ms 30044 KB Output is correct
24 Correct 16 ms 30044 KB Output is correct
25 Correct 15 ms 30044 KB Output is correct
26 Correct 15 ms 30044 KB Output is correct
27 Correct 15 ms 30044 KB Output is correct
28 Correct 15 ms 30044 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30044 KB Output is correct
2 Correct 296 ms 50864 KB Output is correct
3 Correct 461 ms 48684 KB Output is correct
4 Correct 413 ms 64548 KB Output is correct
5 Correct 373 ms 49484 KB Output is correct
6 Correct 432 ms 48136 KB Output is correct
7 Correct 490 ms 47492 KB Output is correct
8 Correct 378 ms 51260 KB Output is correct
9 Correct 380 ms 70992 KB Output is correct
10 Correct 509 ms 83884 KB Output is correct
11 Correct 292 ms 50616 KB Output is correct
12 Correct 510 ms 48372 KB Output is correct
13 Correct 322 ms 54968 KB Output is correct
14 Correct 391 ms 52648 KB Output is correct
15 Correct 401 ms 49024 KB Output is correct
16 Correct 414 ms 48164 KB Output is correct
17 Correct 458 ms 46908 KB Output is correct
18 Correct 15 ms 30044 KB Output is correct
19 Correct 15 ms 30204 KB Output is correct
20 Correct 15 ms 30044 KB Output is correct
21 Correct 15 ms 30044 KB Output is correct
22 Correct 15 ms 30128 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30044 KB Output is correct
2 Correct 296 ms 50864 KB Output is correct
3 Correct 461 ms 48684 KB Output is correct
4 Correct 413 ms 64548 KB Output is correct
5 Correct 373 ms 49484 KB Output is correct
6 Correct 432 ms 48136 KB Output is correct
7 Correct 490 ms 47492 KB Output is correct
8 Correct 378 ms 51260 KB Output is correct
9 Correct 380 ms 70992 KB Output is correct
10 Correct 509 ms 83884 KB Output is correct
11 Correct 292 ms 50616 KB Output is correct
12 Correct 510 ms 48372 KB Output is correct
13 Correct 322 ms 54968 KB Output is correct
14 Correct 391 ms 52648 KB Output is correct
15 Correct 401 ms 49024 KB Output is correct
16 Correct 414 ms 48164 KB Output is correct
17 Correct 458 ms 46908 KB Output is correct
18 Correct 15 ms 30044 KB Output is correct
19 Correct 15 ms 30204 KB Output is correct
20 Correct 15 ms 30044 KB Output is correct
21 Correct 15 ms 30044 KB Output is correct
22 Correct 15 ms 30128 KB Output is correct
23 Correct 14 ms 30040 KB Output is correct
24 Correct 355 ms 50400 KB Output is correct
25 Correct 562 ms 48512 KB Output is correct
26 Correct 419 ms 75092 KB Output is correct
27 Correct 381 ms 49164 KB Output is correct
28 Correct 541 ms 47876 KB Output is correct
29 Correct 469 ms 48308 KB Output is correct
30 Correct 380 ms 56696 KB Output is correct
31 Correct 411 ms 64336 KB Output is correct
32 Correct 528 ms 96640 KB Output is correct
33 Correct 335 ms 50784 KB Output is correct
34 Correct 596 ms 47716 KB Output is correct
35 Correct 16 ms 30040 KB Output is correct
36 Correct 17 ms 30044 KB Output is correct
37 Correct 15 ms 30040 KB Output is correct
38 Correct 16 ms 30040 KB Output is correct
39 Correct 16 ms 30040 KB Output is correct
40 Correct 15 ms 30068 KB Output is correct
41 Correct 15 ms 30044 KB Output is correct
42 Correct 17 ms 30044 KB Output is correct
43 Correct 14 ms 30116 KB Output is correct
44 Correct 15 ms 30040 KB Output is correct
45 Correct 15 ms 30296 KB Output is correct
46 Correct 19 ms 30132 KB Output is correct
47 Correct 15 ms 30040 KB Output is correct
48 Correct 15 ms 30044 KB Output is correct
49 Correct 14 ms 30200 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30044 KB Output is correct
2 Correct 687 ms 106396 KB Output is correct
3 Correct 2128 ms 618928 KB Output is correct
4 Correct 918 ms 180928 KB Output is correct
5 Correct 1865 ms 53540 KB Output is correct
6 Correct 1263 ms 75812 KB Output is correct
7 Correct 797 ms 94464 KB Output is correct
8 Correct 387 ms 123772 KB Output is correct
9 Correct 639 ms 98096 KB Output is correct
10 Correct 2017 ms 651152 KB Output is correct
11 Correct 924 ms 52600 KB Output is correct
12 Execution timed out 4045 ms 113208 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30040 KB Output is correct
2 Correct 632 ms 98688 KB Output is correct
3 Correct 1883 ms 633132 KB Output is correct
4 Correct 865 ms 169552 KB Output is correct
5 Correct 1794 ms 56476 KB Output is correct
6 Correct 1175 ms 82076 KB Output is correct
7 Correct 878 ms 89436 KB Output is correct
8 Correct 423 ms 125644 KB Output is correct
9 Correct 669 ms 111500 KB Output is correct
10 Correct 2039 ms 655048 KB Output is correct
11 Correct 925 ms 55148 KB Output is correct
12 Execution timed out 4054 ms 88152 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30040 KB Output is correct
2 Correct 14 ms 30040 KB Output is correct
3 Correct 15 ms 30044 KB Output is correct
4 Correct 19 ms 30616 KB Output is correct
5 Correct 18 ms 30300 KB Output is correct
6 Correct 18 ms 30300 KB Output is correct
7 Correct 17 ms 30296 KB Output is correct
8 Correct 17 ms 30300 KB Output is correct
9 Correct 15 ms 30044 KB Output is correct
10 Correct 15 ms 30044 KB Output is correct
11 Correct 17 ms 30076 KB Output is correct
12 Correct 15 ms 30044 KB Output is correct
13 Correct 15 ms 30044 KB Output is correct
14 Correct 15 ms 30124 KB Output is correct
15 Correct 15 ms 30044 KB Output is correct
16 Correct 15 ms 30188 KB Output is correct
17 Correct 15 ms 30044 KB Output is correct
18 Correct 15 ms 30044 KB Output is correct
19 Correct 14 ms 30208 KB Output is correct
20 Correct 15 ms 30044 KB Output is correct
21 Correct 15 ms 30044 KB Output is correct
22 Correct 15 ms 30044 KB Output is correct
23 Correct 16 ms 30044 KB Output is correct
24 Correct 16 ms 30044 KB Output is correct
25 Correct 15 ms 30044 KB Output is correct
26 Correct 15 ms 30044 KB Output is correct
27 Correct 15 ms 30044 KB Output is correct
28 Correct 15 ms 30044 KB Output is correct
29 Correct 15 ms 30044 KB Output is correct
30 Correct 296 ms 50864 KB Output is correct
31 Correct 461 ms 48684 KB Output is correct
32 Correct 413 ms 64548 KB Output is correct
33 Correct 373 ms 49484 KB Output is correct
34 Correct 432 ms 48136 KB Output is correct
35 Correct 490 ms 47492 KB Output is correct
36 Correct 378 ms 51260 KB Output is correct
37 Correct 380 ms 70992 KB Output is correct
38 Correct 509 ms 83884 KB Output is correct
39 Correct 292 ms 50616 KB Output is correct
40 Correct 510 ms 48372 KB Output is correct
41 Correct 322 ms 54968 KB Output is correct
42 Correct 391 ms 52648 KB Output is correct
43 Correct 401 ms 49024 KB Output is correct
44 Correct 414 ms 48164 KB Output is correct
45 Correct 458 ms 46908 KB Output is correct
46 Correct 15 ms 30044 KB Output is correct
47 Correct 15 ms 30204 KB Output is correct
48 Correct 15 ms 30044 KB Output is correct
49 Correct 15 ms 30044 KB Output is correct
50 Correct 15 ms 30128 KB Output is correct
51 Correct 14 ms 30040 KB Output is correct
52 Correct 355 ms 50400 KB Output is correct
53 Correct 562 ms 48512 KB Output is correct
54 Correct 419 ms 75092 KB Output is correct
55 Correct 381 ms 49164 KB Output is correct
56 Correct 541 ms 47876 KB Output is correct
57 Correct 469 ms 48308 KB Output is correct
58 Correct 380 ms 56696 KB Output is correct
59 Correct 411 ms 64336 KB Output is correct
60 Correct 528 ms 96640 KB Output is correct
61 Correct 335 ms 50784 KB Output is correct
62 Correct 596 ms 47716 KB Output is correct
63 Correct 16 ms 30040 KB Output is correct
64 Correct 17 ms 30044 KB Output is correct
65 Correct 15 ms 30040 KB Output is correct
66 Correct 16 ms 30040 KB Output is correct
67 Correct 16 ms 30040 KB Output is correct
68 Correct 15 ms 30068 KB Output is correct
69 Correct 15 ms 30044 KB Output is correct
70 Correct 17 ms 30044 KB Output is correct
71 Correct 14 ms 30116 KB Output is correct
72 Correct 15 ms 30040 KB Output is correct
73 Correct 15 ms 30296 KB Output is correct
74 Correct 19 ms 30132 KB Output is correct
75 Correct 15 ms 30040 KB Output is correct
76 Correct 15 ms 30044 KB Output is correct
77 Correct 14 ms 30200 KB Output is correct
78 Correct 16 ms 30044 KB Output is correct
79 Correct 687 ms 106396 KB Output is correct
80 Correct 2128 ms 618928 KB Output is correct
81 Correct 918 ms 180928 KB Output is correct
82 Correct 1865 ms 53540 KB Output is correct
83 Correct 1263 ms 75812 KB Output is correct
84 Correct 797 ms 94464 KB Output is correct
85 Correct 387 ms 123772 KB Output is correct
86 Correct 639 ms 98096 KB Output is correct
87 Correct 2017 ms 651152 KB Output is correct
88 Correct 924 ms 52600 KB Output is correct
89 Execution timed out 4045 ms 113208 KB Time limit exceeded
90 Halted 0 ms 0 KB -