Submission #558482

#	Time	Username	Problem	Language	Result	Execution time	Memory
558482		DanShaders	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	4082 ms	233700 KiB

sprinkler

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#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, DIFF = 1;

vector<int> g[N];
int h[N], sz[N];
char used[N];

struct CentroidNode {
	int parent;
	vector<pair<int, int>> od, pd;
	vector<int> op[DIFF], pp[DIFF];
	vector<ll> oi, pi;
} tc[N];

int dfs_sz(int u, int p = -1) {
	if (used[u]) {
		return 0;
	}
	sz[u] = 1;
	for (int v : g[u]) {
		if (v == p) {
			continue;
		}
		sz[u] += dfs_sz(v, u);
	}
	return sz[u];
}

int dfs_find_centroid(int u, int csz, int p = -1) {
	for (int v : g[u]) {
		if (v != p && !used[v] && 2 * sz[v] > csz) {
			return dfs_find_centroid(v, csz, u);
		}
	}
	return u;
}

int croot;

void dfs_centroid(int root, int parent = -1) {
	int centroid = dfs_find_centroid(root, dfs_sz(root));
	auto &node = tc[centroid];
	node.parent = parent;
	if (parent == -1) {
		croot = centroid;
	}

	// normal_queue<tuple<int, int, int>> bfsp;
	// bfsp.push({1, root, -1});
	// while (sz(bfsp)) {
	// 	auto [d, u, p] = bfsp.top();
	// 	bfsp.pop();
	// 	node.pd.push_back({d, u});
	// 	for (int v : g[u]) {
	// 		if (!used[v] && v != p) {
	// 			bfsp.push({d + 1, v, u});
	// 		}
	// 	}
	// }
	normal_queue<tuple<int, int, int>> bfso;
	bfso.push({0, centroid, -1});
	while (sz(bfso)) {
		auto [d, u, p] = bfso.top();
		bfso.pop();
		node.od.push_back({d, u});
		for (int v : g[u]) {
			if (!used[v] && v != p) {
				bfso.push({d + 1, v, u});
			}
		}
	}
	
	for (int i = 0; i < DIFF; ++i) {
		node.op[i].resize(2 * sz(node.od));
		// node.pp[i].resize(2 * sz(node.od));
	}
	node.oi.resize(2 * sz(node.od), 1);
	// node.pi.resize(2 * sz(node.od), 1);

	used[centroid] = 1;
	for (int v : g[centroid]) {
		if (!used[v]) {
			dfs_centroid(v, centroid);
		}
	}
}

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

void dfs_euler(int u, int d = 0, int p = -1) {
	order[u] = timer;
	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<pair<int, int>> factor(int x) {
	vector<pair<int, int>> res;
	for (int i = 2; i * i <= x; ++i) {
		if (x % i == 0) {
			res.push_back({i, 0});
			while (x % i == 0) {
				++res.back().y;
				x /= i;
			}
		}
	}
	if (x != 1) {
		res.push_back({x, 1});
	}
	return res;
}

pair<vector<int>, int> get_pw(int x, const vector<pair<int, int>> &fact) {
	vector<int> pw;
	for (auto [prime, _] : fact) {
		pw.push_back(0);
		while (x % prime == 0) {
			x /= prime;
			++pw.back();
		}
	}
	return {pw, x};
}

void exgcd(int a, int b, ll &x, ll &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, x, y);
	ll nw = x - (a / b) * y;
	x = y;
	y = nw;
}

int diff;
ll l;

template <typename T>
void tdo(int l, int r, int s, T func) {
	l += s;
	r += s;
	while (l <= r) {
		if (l & 1)	func(l);
		if (!(r & 1))	func(r);
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}

void apply_for(const vector<int> &part, int ineq, int inv, int u, int x, int d) {
	auto &node = tc[u];

	int dst = d - dist(u, x);
	int bound = int(lower_bound(all(node.od), pair{dst + 1, -1}) - begin(node.od));
	for (int i = 0; i < diff; ++i) {
		if (part[i] == 0) {
			continue;
		}
		tdo(0, bound - 1, sz(node.od), [&](int j) {
			node.op[i][j] += part[i];
		});
		// for (int j = 0; j < bound; ++j) {
		// 	node.op[i][j] += part[i];
		// }
	}
	if (ineq != 1) {
		tdo(0, bound - 1, sz(node.od), [&](int j) {
			(node.oi[j] *= ineq) %= l;
		});
		// for (int j = 0; j < bound; ++j) {
		// 	(node.oi[j] *= ineq) %= l;
		// }
	}

	// if (node.parent == -1) {
	// 	return;
	// }

	// dst = d - dist(node.parent, x);
	// bound = int(lower_bound(all(node.pd), pair{dst + 1, -1}) - begin(node.pd));
	// for (int i = 0; i < diff; ++i) {
	// 	if (part[i] == 0) {
	// 		continue;
	// 	}
	// 	// for (int j = 0; j < bound; ++j) {
	// 	// 	node.pp[i][j] -= part[i];
	// 	// }
	// 	tdo(0, bound - 1, sz(node.od), [&](int j) {
	// 		node.pp[i][j] -= part[i];
	// 	});
	// }
	// if (inv != 1) {
	// 	// for (int j = 0; j < bound; ++j) {
	// 	// 	(node.pi[j] *= inv) %= l;
	// 	// }
	// 	tdo(0, bound - 1, sz(node.od), [&](int j) {
	// 		(node.pi[j] *= inv) %= l;
	// 	});
	// }
}

void count_for(vector<int> &part, ll &ineq, int u, int x) {
	const auto &node = tc[u];

	int i = int(lower_bound(all(node.od), pair{dist(u, x), x}) - begin(node.od));
	i += sz(node.od);

	while (i) {
		for (int j = 0; j < diff; ++j) {
			part[j] += node.op[j][i];
		}
		(ineq *= node.oi[i]) %= l;
		i /= 2;
	}

	// if (node.parent == -1) {
	// 	return;
	// }

	// i = int(lower_bound(all(node.pd), pair{dist(node.parent, x), x}) - begin(node.pd));
	// i += sz(node.od);

	// while (i) {
	// 	for (int j = 0; j < diff; ++j) {
	// 		part[j] += node.pp[j][i];
	// 	}
	// 	(ineq *= node.pi[i]) %= l;
	// 	i /= 2;
	// }
}

ll fpow(ll a, ll b) {
	ll c = 1;
	for (int i = 1; i <= b; i *= 2) {
		if (b & i) {
			(c *= a) %= l;
		}
		(a *= a) %= l;
	}
	return c;
}

signed main() {
#ifdef DEBUG
	freopen("output.txt", "w", stdout);
#endif
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n >> l;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	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;
	}
	dfs_centroid(0);
	int queries;
	cin >> queries;
	auto fact = factor(int(l));
	diff = sz(fact);

	diff = 1;
	fact = {{l, 1}};

	while (queries--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			--x;
			if (!w) {
				w = int(l);
			}
			auto [part, ineq] = get_pw(w, fact);
			ll inv, tmp;
			exgcd(ineq, int(l), inv, tmp);
			inv = (inv % l + l) % l;

			int curr = x;
			while (curr != -1) {
				apply_for(part, ineq, int(inv), curr, x, d);
				curr = tc[curr].parent;
			}
		} else {
			int x;
			cin >> x;
			--x;
			vector<int> part(diff);
			ll ineq = 1;
			int curr = x;
			while (curr != -1) {
				count_for(part, ineq, curr, x);
				curr = tc[curr].parent;
			}

			ll res = 1;
			for (int i = 0; i < diff; ++i) {
				(res *= fpow(fact[i].x, part[i])) %= l;
			}
			(res *= ineq) %= l;
			cout << (h[x] * res) % l << "\n";
			// for (int u : part) {
			// 	cout << u << " ";
			// }
			// cout << ineq << "\n";
		}
	}
	cerr << clock() << 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