Submission #922038

#	Time	Username	Problem	Language	Result	Execution time	Memory
922038		OAleksa	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	881 ms	97492 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 2e5 + 69;
const int D = 42;
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;
			a += 40;
			b += 40;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 41;i <= 40 + n;i++)
			cin >> a[i];
		for (int i = 1;i <= 40 + n;i++) {
			for (int j = 0;j < D;j++)
				sum[i][j] = 1;
		}
		for (int i = 1;i <= 40;i++) {
			g[i].push_back(i + 1);
			g[i + 1].push_back(i);
		}
		dfs(1, 0);
		cin >> q;
		while (q--) {
			int t;
			cin >> t;
			if (t == 1) {
				int x, d, w;
				cin >> x >> d >> w;
				x += 40;
				int t = x, j = 0;
				while (t != 0 && j <= d) {
					sum[t][d - j] = (sum[t][d - j] * w) % L;
					if (j != d)
						sum[t][d - j - 1] = (sum[t][d - j - 1] * w) % L;
					j++;
					t = par[t];
				}
			}
			else {
				int x;
				cin >> x;
				x += 40;
				int ans = a[x];
				int t = x, j = 0;
				while (t != 0 && j < D) {
					ans = (ans * sum[t][j]) % L;
					j++;
					t = par[t];
				}
				cout << ans << '\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