Submission #561256

#	Time	Username	Problem	Language	Result	Execution time	Memory
561256		DanShaders	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	1014 ms	104240 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];
int lnk[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);
		lnk[u] = sz(layer[dst + 1]);
		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 where, int index) {
				int lef = -1, rig = index;
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						rig = mid;
					} else {
						lef = mid;
					}
				}
				bool flag = (rig != index);
				upd(layer_start[where] + rig, layer_start[where] + index - 1, w);
			
				lef = index - 1, 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;
					}
				}
				flag |= index - 1 != lef;
				upd(layer_start[where] + index, layer_start[where] + lef, w);
				return flag;
			};

			for (int u = parent[x]; u != -1; u = parent[u]) {
				if (!upd_with_base(inv[u].x, inv[u].y)) {
					break;
				}
			}
			int where = inv[x].x, index = inv[x].y;
			while (1) {
				if (!upd_with_base(where, index)) {
					break;
				}
				if (index == sz(layer[where])) {
					++where;
					index = sz(layer[where]);
				} else {
					index = lnk[layer[where][index]];
					++where;
				}
			}
		} 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: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17