oj.uz

Submission #558476

# Submission time Handle Problem Language Result Execution time Memory
558476 2022-05-07T12:38:48 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 635328 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(sz(node.od));
		node.pp[i].resize(sz(node.od));
	}
	node.oi.resize(sz(node.od), 1);
	node.pi.resize(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;

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;
		}
		for (int j = 0; j < bound; ++j) {
			node.op[i][j] += part[i];
		}
	}
	if (ineq != 1) {
		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];
		}
	}
	if (inv != 1) {
		for (int j = 0; j < bound; ++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));

	// cout << "at " << u << " with " << x << endl;
	// for (auto [d, v] : node.od) {
	// 	cout << d << ":" << v << " ";
	// }
	// cout << endl;

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

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

	i = int(lower_bound(all(node.pd), pair{dist(node.parent, x), x}) - begin(node.pd));
	for (int j = 0; j < diff; ++j) {
		part[j] += node.pp[j][i];
	}
	(ineq *= node.pi[i]) %= l;
}

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][i] += part[j];
		}
		(node.oi[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 50 ms 109840 KB Output is correct
2 Correct 50 ms 109844 KB Output is correct
3 Correct 54 ms 109972 KB Output is correct
4 Correct 58 ms 111672 KB Output is correct
5 Correct 61 ms 111496 KB Output is correct
6 Correct 72 ms 111260 KB Output is correct
7 Correct 66 ms 111284 KB Output is correct
8 Correct 57 ms 111060 KB Output is correct
9 Correct 52 ms 109912 KB Output is correct
10 Correct 51 ms 109904 KB Output is correct
11 Correct 51 ms 109948 KB Output is correct
12 Correct 53 ms 109904 KB Output is correct
13 Correct 59 ms 109900 KB Output is correct
14 Correct 55 ms 109860 KB Output is correct
15 Correct 66 ms 109976 KB Output is correct
16 Correct 51 ms 109980 KB Output is correct
17 Correct 52 ms 110028 KB Output is correct
18 Correct 52 ms 109940 KB Output is correct
19 Correct 55 ms 109876 KB Output is correct
20 Correct 61 ms 109964 KB Output is correct
21 Correct 53 ms 109988 KB Output is correct
22 Correct 59 ms 109896 KB Output is correct
23 Correct 61 ms 109984 KB Output is correct
24 Correct 50 ms 109948 KB Output is correct
25 Correct 54 ms 109976 KB Output is correct
26 Correct 62 ms 109964 KB Output is correct
27 Correct 51 ms 109940 KB Output is correct
28 Correct 54 ms 109992 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 109956 KB Output is correct
2 Execution timed out 4131 ms 631912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109840 KB Output is correct
2 Correct 50 ms 109844 KB Output is correct
3 Correct 54 ms 109972 KB Output is correct
4 Correct 58 ms 111672 KB Output is correct
5 Correct 61 ms 111496 KB Output is correct
6 Correct 72 ms 111260 KB Output is correct
7 Correct 66 ms 111284 KB Output is correct
8 Correct 57 ms 111060 KB Output is correct
9 Correct 52 ms 109912 KB Output is correct
10 Correct 51 ms 109904 KB Output is correct
11 Correct 51 ms 109948 KB Output is correct
12 Correct 53 ms 109904 KB Output is correct
13 Correct 59 ms 109900 KB Output is correct
14 Correct 55 ms 109860 KB Output is correct
15 Correct 66 ms 109976 KB Output is correct
16 Correct 51 ms 109980 KB Output is correct
17 Correct 52 ms 110028 KB Output is correct
18 Correct 52 ms 109940 KB Output is correct
19 Correct 55 ms 109876 KB Output is correct
20 Correct 61 ms 109964 KB Output is correct
21 Correct 53 ms 109988 KB Output is correct
22 Correct 59 ms 109896 KB Output is correct
23 Correct 61 ms 109984 KB Output is correct
24 Correct 50 ms 109948 KB Output is correct
25 Correct 54 ms 109976 KB Output is correct
26 Correct 62 ms 109964 KB Output is correct
27 Correct 51 ms 109940 KB Output is correct
28 Correct 54 ms 109992 KB Output is correct
29 Correct 52 ms 109968 KB Output is correct
30 Execution timed out 4075 ms 545352 KB Time limit exceeded
31 Halted 0 ms 0 KB -