Submission #896842

#	Time	Username	Problem	Language	Result	Execution time	Memory
896842		TAhmed33	Sprinkler (JOI22_sprinkler)	C++98	38 / 100	858 ms	35112 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int p[MAXN], h[MAXN], n, l, q;
int lazy[MAXN], lazy2[MAXN];
void fix (int pos, int par) {
	p[pos] = par;
	for (int j = 0; j < (int)adj[pos].size(); j++) {
		if (adj[pos][j] == par) {
			adj[pos].erase(adj[pos].begin() + j);
			break;
		}
	}
	for (auto j : adj[pos]) {
		fix(j, pos);
	}
}
int mul (int a, int b) {
	return (a * 1ll * b) % l;
}
int main () {
	cin >> n >> l;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) lazy[i] = lazy2[i] = 1;
	fix(1, -1);
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			if (d == 0) {
				h[x] = mul(h[x], w); 
			} else if (d == 1) {
				if (p[x] != -1) {
					h[p[x]] = mul(h[p[x]], w);
				}
				h[x] = mul(h[x], w);
				lazy[x] = mul(lazy[x], w);
			} else if (d == 2) {
				if (p[x] == -1) {
					lazy2[x] = mul(lazy2[x], w);
					h[x] = mul(h[x], w);
				} else if (p[p[x]] == -1) {
					lazy2[x] = mul(lazy2[x], w);
					h[p[x]] = mul(h[p[x]], w);
					lazy[p[x]] = mul(lazy[p[x]], w);
				} else {
					lazy2[x] = mul(lazy2[x], w);
					lazy[p[x]] = mul(lazy[p[x]], w);
					h[p[x]] = mul(h[p[x]], w);
					h[p[p[x]]] = mul(h[p[p[x]]], w);
				}
			}
		} else {
			int x;
			cin >> x;
			int z = h[x];
			if (p[x] != -1) {
				z = mul(z, lazy[p[x]]);
				z = mul(z, lazy2[p[x]]);
				if (p[p[x]] != -1) {
					z = mul(z, lazy2[p[p[x]]]);
				}
			}
			cout << z << '\n';
		}
	}
}

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