Submission #921250

#	Time	Username	Problem	Language	Result	Execution time	Memory
921250		OAleksa	Sprinkler (JOI22_sprinkler)	C++14	0 / 100	1753 ms	62008 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int D = 44;
int sum[N][D];
int n, L, a[N], par[N], q;
vector<int> g[N];
void dfs(int v, int p) {
	par[v] = p;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> L;
		for (int i = 1;i <= n - 1;i++) {
			int a, b;
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 1;i <= n;i++)
			cin >> a[i];
		for (int i = 1;i <= n;i++) {
			for (int j = 0;j < D;j++)
				sum[i][j] = 1;
		}
		dfs(1, 0);
		cin >> q;
		while (q--) {
			int t;
			cin >> t;
			if (t == 1) {
				int x, d, w;
				cin >> x >> d >> w;
				int t = x, j = 0;
				while (t != 0 && j <= d) {
					a[t] = (a[t] * w) % L;
					j++;
					t = par[t];
				}
				sum[x][d] = (sum[x][d] * w) % L;
			}
			else {
				int x;
				cin >> x;
				int ans = a[x];
				int t = par[x], j = 1;
				while (t != 0 && j < D) {
					for (int i = j;i < D;i++)
						ans = (ans * sum[t][i]) % L;
					t = par[x];
					j++;
				}
				cout << ans << '\n';
			}
		}
  }
  return 0;
}

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