oj.uz

Submission #558478

# Submission time Handle Problem Language Result Execution time Memory
558478 2022-05-07T12:45:06 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 904292 KB 
//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, DIFF = 9;

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() {
	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];
		if (h[i] == 0) {
			h[i] = int(l);
		}
	}
	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);

	auto &node = tc[croot];
	for (int i = 0; i < n; ++i) {
		auto [part, ineq] = get_pw(h[node.od[i].y], fact);

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

	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 << res << "\n";
			// for (int u : part) {
			// 	cout << u << " ";
			// }
			// cout << ineq << "\n";
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 109872 KB Output is correct
2 Correct 50 ms 109872 KB Output is correct
3 Correct 53 ms 109952 KB Output is correct
4 Correct 59 ms 112256 KB Output is correct
5 Correct 57 ms 111948 KB Output is correct
6 Correct 55 ms 111772 KB Output is correct
7 Correct 57 ms 111652 KB Output is correct
8 Correct 54 ms 111176 KB Output is correct
9 Correct 54 ms 109916 KB Output is correct
10 Correct 56 ms 109904 KB Output is correct
11 Correct 52 ms 109984 KB Output is correct
12 Correct 50 ms 109956 KB Output is correct
13 Correct 51 ms 109980 KB Output is correct
14 Correct 57 ms 109932 KB Output is correct
15 Correct 58 ms 109904 KB Output is correct
16 Correct 54 ms 110012 KB Output is correct
17 Correct 52 ms 109984 KB Output is correct
18 Correct 51 ms 110044 KB Output is correct
19 Correct 55 ms 109952 KB Output is correct
20 Correct 54 ms 109900 KB Output is correct
21 Correct 57 ms 109916 KB Output is correct
22 Correct 55 ms 110016 KB Output is correct
23 Correct 52 ms 109976 KB Output is correct
24 Correct 53 ms 110028 KB Output is correct
25 Correct 55 ms 109900 KB Output is correct
26 Correct 60 ms 109984 KB Output is correct
27 Correct 56 ms 109896 KB Output is correct
28 Correct 54 ms 109956 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109868 KB Output is correct
2 Execution timed out 4107 ms 748428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109868 KB Output is correct
2 Execution timed out 4107 ms 748428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 109884 KB Output is correct
2 Execution timed out 4124 ms 904292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 109892 KB Output is correct
2 Execution timed out 4128 ms 898396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 109872 KB Output is correct
2 Correct 50 ms 109872 KB Output is correct
3 Correct 53 ms 109952 KB Output is correct
4 Correct 59 ms 112256 KB Output is correct
5 Correct 57 ms 111948 KB Output is correct
6 Correct 55 ms 111772 KB Output is correct
7 Correct 57 ms 111652 KB Output is correct
8 Correct 54 ms 111176 KB Output is correct
9 Correct 54 ms 109916 KB Output is correct
10 Correct 56 ms 109904 KB Output is correct
11 Correct 52 ms 109984 KB Output is correct
12 Correct 50 ms 109956 KB Output is correct
13 Correct 51 ms 109980 KB Output is correct
14 Correct 57 ms 109932 KB Output is correct
15 Correct 58 ms 109904 KB Output is correct
16 Correct 54 ms 110012 KB Output is correct
17 Correct 52 ms 109984 KB Output is correct
18 Correct 51 ms 110044 KB Output is correct
19 Correct 55 ms 109952 KB Output is correct
20 Correct 54 ms 109900 KB Output is correct
21 Correct 57 ms 109916 KB Output is correct
22 Correct 55 ms 110016 KB Output is correct
23 Correct 52 ms 109976 KB Output is correct
24 Correct 53 ms 110028 KB Output is correct
25 Correct 55 ms 109900 KB Output is correct
26 Correct 60 ms 109984 KB Output is correct
27 Correct 56 ms 109896 KB Output is correct
28 Correct 54 ms 109956 KB Output is correct
29 Correct 50 ms 109868 KB Output is correct
30 Execution timed out 4107 ms 748428 KB Time limit exceeded
31 Halted 0 ms 0 KB -