oj.uz

Submission #558480

# Submission time Handle Problem Language Result Execution time Memory
558480 2022-05-07T12:46:55 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 893660 KB 
//bs:sanitizers
#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 = 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 66 ms 109960 KB Output is correct
2 Correct 67 ms 109860 KB Output is correct
3 Correct 59 ms 109960 KB Output is correct
4 Correct 64 ms 112340 KB Output is correct
5 Correct 68 ms 111984 KB Output is correct
6 Correct 65 ms 111652 KB Output is correct
7 Correct 74 ms 111588 KB Output is correct
8 Correct 68 ms 111180 KB Output is correct
9 Correct 61 ms 109900 KB Output is correct
10 Correct 61 ms 109980 KB Output is correct
11 Correct 62 ms 109940 KB Output is correct
12 Correct 63 ms 109964 KB Output is correct
13 Correct 79 ms 109936 KB Output is correct
14 Correct 67 ms 109856 KB Output is correct
15 Correct 62 ms 109968 KB Output is correct
16 Correct 60 ms 110080 KB Output is correct
17 Correct 60 ms 110004 KB Output is correct
18 Correct 65 ms 109912 KB Output is correct
19 Correct 62 ms 109868 KB Output is correct
20 Correct 65 ms 109924 KB Output is correct
21 Correct 63 ms 109968 KB Output is correct
22 Correct 60 ms 109948 KB Output is correct
23 Correct 65 ms 109916 KB Output is correct
24 Correct 63 ms 109964 KB Output is correct
25 Correct 64 ms 109880 KB Output is correct
26 Correct 73 ms 109936 KB Output is correct
27 Correct 64 ms 109908 KB Output is correct
28 Correct 59 ms 109900 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 109968 KB Output is correct
2 Execution timed out 4043 ms 748936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 109968 KB Output is correct
2 Execution timed out 4043 ms 748936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 109976 KB Output is correct
2 Execution timed out 4097 ms 893660 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 109940 KB Output is correct
2 Execution timed out 4077 ms 891820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 109960 KB Output is correct
2 Correct 67 ms 109860 KB Output is correct
3 Correct 59 ms 109960 KB Output is correct
4 Correct 64 ms 112340 KB Output is correct
5 Correct 68 ms 111984 KB Output is correct
6 Correct 65 ms 111652 KB Output is correct
7 Correct 74 ms 111588 KB Output is correct
8 Correct 68 ms 111180 KB Output is correct
9 Correct 61 ms 109900 KB Output is correct
10 Correct 61 ms 109980 KB Output is correct
11 Correct 62 ms 109940 KB Output is correct
12 Correct 63 ms 109964 KB Output is correct
13 Correct 79 ms 109936 KB Output is correct
14 Correct 67 ms 109856 KB Output is correct
15 Correct 62 ms 109968 KB Output is correct
16 Correct 60 ms 110080 KB Output is correct
17 Correct 60 ms 110004 KB Output is correct
18 Correct 65 ms 109912 KB Output is correct
19 Correct 62 ms 109868 KB Output is correct
20 Correct 65 ms 109924 KB Output is correct
21 Correct 63 ms 109968 KB Output is correct
22 Correct 60 ms 109948 KB Output is correct
23 Correct 65 ms 109916 KB Output is correct
24 Correct 63 ms 109964 KB Output is correct
25 Correct 64 ms 109880 KB Output is correct
26 Correct 73 ms 109936 KB Output is correct
27 Correct 64 ms 109908 KB Output is correct
28 Correct 59 ms 109900 KB Output is correct
29 Correct 59 ms 109968 KB Output is correct
30 Execution timed out 4043 ms 748936 KB Time limit exceeded
31 Halted 0 ms 0 KB -