Submission #739816

#	Time	Username	Problem	Language	Result	Execution time	Memory
739816		myrcella	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	735 ms	68012 KiB

sprinkler

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
int mod;
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;
int fa[maxn];
vector <int> edge[maxn];
int tag[maxn][44];
int n;
int w[maxn];

void dfs(int u,int lst) {
	fa[u] = lst;
	rep(i,0,41) tag[u][i] = 1;
	for (int v:edge[u]) {
		if (v==lst) continue;
		dfs(v,u);
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>mod;
	rep(i,1,n) {
		int u,v;cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	dfs(1,-1);
	rep(i,1,n+1) cin>>w[i];
	int _;cin>>_;
	while (_--) {
		int x,y;
		cin>>x>>y;
		if (x==1) {
			int d,z;cin>>d>>z;
			int cur = y;
			while (d>=0 and cur!=-1) {
				tag[cur][d] = 1ll*tag[cur][d]*z%mod;
				if (d!=0) tag[cur][d-1] = 1ll*tag[cur][d-1]*z%mod;
				d--;
				cur = fa[cur];
			}
			d--;
			while (d>=0) tag[1][d] = 1ll*tag[1][d]*z%mod,d--;
		}
		else {
			int ret = w[y];
			int cur = y;int dis = 0;
			while (cur!=-1 and dis<=40) {
				ret = 1ll*ret*tag[cur][dis]%mod;
				dis++;
				cur = fa[cur];
			}
			cout<<ret<<"\n";
		}
	}
	return 0;
}

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