Submission #1140830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140830		KK_1729	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	798 ms	94276 KiB

sprinkler

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

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}


void solve(){
	int n, l; cin >> n >> l;
	vector<vector<int>> graph(n+1);

	FOR(i,0,n-1){
		int a, b; cin >> a >> b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	vector<int> par(n+50);
	par[1] = n+1;
	FOR(i,1,42){
		par[n+i] = n+i+1;
	}
	stack<int> s;
	// vector<int> dep(n+50);
	s.push(1);
	vector<int> visited(n+50);
	while (!s.empty()){
		int current = s.top();
		s.pop();
		if (visited[current]) continue;
		for (auto x: graph[current]){
			if (visited[x]) continue;
			par[x] = current;
			// dep[x] = dep[current]+1;
			s.push(x);
		}
		visited[current] = 1;
	}
	vector<int> h(n+50);
	FOR(i,1,n+1) cin >> h[i];

	vector<vector<int>> a(n+50, vector<int>(42, 1));
	int q; cin >> q;
	FOR(e,0,q){
		int t; cin >> t;
		if (t == 1){
			int x, d, w; cin >> x >> d >> w;
			int height = 0;
			while (height <= d){
				a[x][d-height] *= w;
				a[x][d-height] %= l;

				if (d-height){
					a[x][d-height-1] *= w;
					a[x][d-height-1] %= l;
				}
				x = par[x];
				height++;
			}
		}else{
			int x; cin >> x;
			int height = 0;
			int curr = h[x];
			while (height <= 41){
				curr *= a[x][height];
				curr %= l;
				x = par[x];
				height++;
			}
			cout << curr << endl;
		}

		// cout << e << " a " << a[1][0] << endl;
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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