Submission #561245

#	Time	Username	Problem	Language	Result	Execution time	Memory
561245		DanShaders	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	4043 ms	113768 KiB

sprinkler

//bs:sanitizers
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 2e5 + 10, EULER = 2 * N, LOG = 19;

int n, modulo;

vector<int> g[N];
int ipow[EULER], depth[N];
pair<int, int> sp[LOG][EULER];
int order[N], timer = 0, parent[N];

void dfs_euler(int u, int d = 0, int p = -1) {
	order[u] = timer;
	parent[u] = p;
	depth[u] = d;
	sp[0][timer++] = {d, u};
	for (int v : g[u]) {
		if (v != p) {
			dfs_euler(v, d + 1, u);
			sp[0][timer++] = {d, u};
		}
	}
}

int lca(int u, int v) {
	if (u == v) {
		return u;
	}
	u = order[u];
	v = order[v];
	if (u > v) {
		swap(u, v);
	}
	++v;
	int pw = ipow[v - u];
	return min(sp[pw][u], sp[pw][v - (1 << pw)]).y;
}

int dist(int u, int v) {
	return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

vector<int> layer[N];
pair<int, int> inv[N];
int layer_start[N];

ll t[2 * N];

int get(int u) {
	auto [x, y] = inv[u];
	return layer_start[x] + y;
}

void upd(int l, int r, int w) {
	l += n;
	r += n;
	while (l <= r) {
		if (l & 1)	(t[l] *= w) %= modulo;
		if (!(r & 1))	(t[r] *= w) %= modulo;
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> modulo;
	fill(t, t + 2 * n, 1);
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	
	dfs_euler(0);
	for (int i = 1; i < LOG; ++i) {
		for (int j = 0; j <= timer - (1 << i); ++j) {
			sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
		}
	}
	for (int i = 2; i <= timer; ++i) {
		ipow[i] = ipow[i / 2] + 1;
	}

	queue<tuple<int, int, int>> bfs;
	bfs.push({0, -1, 0});
	while (sz(bfs)) {
		auto [u, p, dst] = bfs.front();
		bfs.pop();
		inv[u] = {dst, sz(layer[dst])};
		layer[dst].push_back(u);
		for (int v : g[u]) {
			if (v != p) {
				bfs.push({v, u, dst + 1});
			}
		}
	}
	for (int i = 1; i < N; ++i) {
		layer_start[i] = layer_start[i - 1] + sz(layer[i - 1]);
	}

	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		t[get(i) + n] = x;
	}

	int queries;
	cin >> queries;
	while (queries--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			--x;

			auto upd_with_base = [&](int u) {
				int where = inv[u].x;
				int lef = -1, rig = inv[u].y;
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						rig = mid;
					} else {
						lef = mid;
					}
				}
				upd(get(layer[where][rig]), get(u), w);
			
				lef = inv[u].y, rig = sz(layer[where]);
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						lef = mid;
					} else {
						rig = mid;
					}
				}
				upd(get(u) + 1, get(layer[where][lef]), w);
			};

			for (int u = parent[x]; u != -1; u = parent[u]) {
				// cout << "top" << u << endl;
				if (dist(x, u) > d) {
					break;
				}
				upd_with_base(u);
			}
			for (int u = x; u != -1; ) {
				// cout << "bottom" << u << endl;
				if (dist(x, u) > d) {
					break;
				}
				upd_with_base(u);
				
				int q = -1;
				for (int v : g[u]) {
					if (v != parent[u]) {
						q = v;
						break;
					}
				}
				u = q;
			}
		} else {
			int x;
			cin >> x;
			int i = get(x - 1) + n;
			ll res = 1;
			while (i) {
				(res *= t[i]) %= modulo;
				i /= 2;
			}
			cout << res << "\n";
		}
		// for (int j = 0; j < n; ++j) {
		// 	int i = get(j) + n;
		// 	ll res = 1;
		// 	while (i) {
		// 		(res *= t[i]) %= modulo;
		// 		i /= 2;
		// 	}
		// 	cout << res << " ";
		// }
		// cout << endl;
	}
}

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