oj.uz

Submission #888978

# Submission time Handle Problem Language Result Execution time Memory
888978 2023-12-18T14:25:26 Z amirhoseinfar1385 Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 61632 KB 
#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<int>seg;
	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 ;
	}
	int pors(int i){
		if(i==0){
			return 1;
		}
		long long ret=pors((i>>1))*seg[i]%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();
			//cout<<u<<" "<<dis<<" "<<w<<" "<<l<<" "<<r<<" "<<lev<<endl; 
			r--;
			seg[lev].add(1,0,seg[lev].sz-1,l,r,w);
		}
		if(z==1){
			u=part[u];
			lev--;
			z=0;
		}
		else{
			lev--;
			z=1;
		}
	}
}

void solve(int u){
	int ind=lower_bound(alll[high[u]].begin(),alll[high[u]].end(),make_pair(stf[u].first,u))-alll[high[u]].begin();
	//cout<<u<<" wtf "<<ind<<endl;
	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;
			upd(u,d,w); 
		}
		else{
			int u;
			cin>>u;
			solve(u);
		}
	}
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25436 KB Output is correct
2 Correct 12 ms 25436 KB Output is correct
3 Correct 13 ms 25436 KB Output is correct
4 Incorrect 14 ms 25432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25432 KB Output is correct
2 Incorrect 294 ms 48092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25432 KB Output is correct
2 Incorrect 294 ms 48092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25424 KB Output is correct
2 Correct 413 ms 61632 KB Output is correct
3 Correct 989 ms 57172 KB Output is correct
4 Correct 465 ms 57660 KB Output is correct
5 Correct 1827 ms 45516 KB Output is correct
6 Correct 1194 ms 45088 KB Output is correct
7 Correct 810 ms 45408 KB Output is correct
8 Correct 332 ms 45352 KB Output is correct
9 Correct 391 ms 55380 KB Output is correct
10 Correct 915 ms 60316 KB Output is correct
11 Correct 815 ms 45228 KB Output is correct
12 Execution timed out 4032 ms 45024 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25432 KB Output is correct
2 Incorrect 363 ms 57308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25436 KB Output is correct
2 Correct 12 ms 25436 KB Output is correct
3 Correct 13 ms 25436 KB Output is correct
4 Incorrect 14 ms 25432 KB Output isn't correct
5 Halted 0 ms 0 KB -