Submission #972762

#	Time	Username	Problem	Language	Result	Execution time	Memory
972762		happy_node	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2000 ms	109344 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5;
int N,L,Q;
int A[MX], B[MX], H[MX];
vector<int> adj[MX];

int par[MX];
ll w[MX][50]; // w and w inverse

void dfs(int v, int p) {
	par[v]=p;
	for(auto u:adj[v]) {
		if(u==p) continue;
		dfs(u,v);
	}
}

void upd(int v, int d, int x) {
	while(d>=0 && v!=0) {
		w[v][d]*=x;
		w[v][d]%=L;
		v=par[v];
		d--;
	}
}

int que(int v) {
	int d=0,p=-1;
	ll res=1;
	while(d<=40 && v!=0) {
		for(int i=d;i<=40;i++) {
			if(par[v]!=0 && i-1>=d+1) continue;
			res*=w[v][i];
			res%=L;
		}
		d++;
		p=v;
		v=par[v];
	}
	return res;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int d=0;d<=41;d++)
			w[i][d]=1;

	cin>>N>>L;
	for(int i=0;i<N-1;i++) {
		cin>>A[i]>>B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}	

	for(int i=1;i<=N;i++) cin>>w[i][0];

	dfs(1,0);

	cin>>Q;
	for(int i=1;i<=Q;i++) {
		int t;
		cin>>t;

		if(t==1) {
			int x,d,w;
			cin>>x>>d>>w;
			upd(x,d,w);
		} else {
			int x;
			cin>>x;
			cout<<que(x)<<'\n';
		}
	}	
}

Compilation message (stderr)

sprinkler.cpp: In function 'int que(int)':
sprinkler.cpp:31:10: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   31 |  int d=0,p=-1;
      |          ^

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17