oj.uz

Submission #558496

# Submission time Handle Problem Language Result Execution time Memory
558496 2022-05-07T13:16:46 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
21 / 100
 3139 ms 233640 KB 
#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, depth, sz;
	vector<int> dst_begin;
	vector<pair<int, int>> pd;
	vector<int> op[DIFF], pp[DIFF];
	vector<ll> oi, pi;
} tc[N];

int where[LOG][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 depth = 0) {
	int centroid = dfs_find_centroid(root, dfs_sz(root));
	auto &node = tc[centroid];
	node.parent = parent;
	node.depth = depth;
	node.sz = sz[root];
	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});
	// 		}
	// 	}
	// }
	queue<tuple<int, int, int>> bfso;
	bfso.push({0, centroid, -1});
	int prev = -1, at = 0;
	while (sz(bfso)) {
		auto [d, u, p] = bfso.front();
		bfso.pop();
		where[depth][u] = at;
		if (prev != d) {
			node.dst_begin.push_back(at);
			prev = d;
		}
		++at;
		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 * node.sz);
		// node.pp[i].resize(2 * node.sz);
	}
	node.oi.resize(2 * node.sz, 1);
	// node.pi.resize(2 * node.sz, 1);

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

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 = dst < 0 ? 0 : (dst + 1 >= sz(node.dst_begin) ? node.sz : node.dst_begin[dst + 1]);
	// int bound = node.sz;
	// cout << bound << endl;
	for (int i = 0; i < diff; ++i) {
		if (part[i] == 0) {
			continue;
		}
		tdo(0, bound - 1, node.sz, [&](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, node.sz, [&](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, node.sz, [&](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, node.sz, [&](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 = where[node.depth][x];
	// int i = node.sz - 1;
	i += node.sz;

	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 += node.sz;

	// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 36308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36396 KB Output is correct
2 Correct 2574 ms 193804 KB Output is correct
3 Correct 1798 ms 188864 KB Output is correct
4 Correct 2607 ms 226872 KB Output is correct
5 Correct 1979 ms 190448 KB Output is correct
6 Correct 1602 ms 174680 KB Output is correct
7 Correct 1446 ms 168020 KB Output is correct
8 Correct 569 ms 130708 KB Output is correct
9 Correct 3139 ms 233640 KB Output is correct
10 Correct 1934 ms 229292 KB Output is correct
11 Correct 2355 ms 193284 KB Output is correct
12 Correct 1535 ms 189732 KB Output is correct
13 Correct 510 ms 130880 KB Output is correct
14 Correct 549 ms 134596 KB Output is correct
15 Correct 613 ms 140140 KB Output is correct
16 Correct 655 ms 144544 KB Output is correct
17 Correct 715 ms 150108 KB Output is correct
18 Correct 18 ms 36308 KB Output is correct
19 Correct 17 ms 36308 KB Output is correct
20 Correct 18 ms 36392 KB Output is correct
21 Correct 17 ms 36376 KB Output is correct
22 Correct 18 ms 36436 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36396 KB Output is correct
2 Correct 2574 ms 193804 KB Output is correct
3 Correct 1798 ms 188864 KB Output is correct
4 Correct 2607 ms 226872 KB Output is correct
5 Correct 1979 ms 190448 KB Output is correct
6 Correct 1602 ms 174680 KB Output is correct
7 Correct 1446 ms 168020 KB Output is correct
8 Correct 569 ms 130708 KB Output is correct
9 Correct 3139 ms 233640 KB Output is correct
10 Correct 1934 ms 229292 KB Output is correct
11 Correct 2355 ms 193284 KB Output is correct
12 Correct 1535 ms 189732 KB Output is correct
13 Correct 510 ms 130880 KB Output is correct
14 Correct 549 ms 134596 KB Output is correct
15 Correct 613 ms 140140 KB Output is correct
16 Correct 655 ms 144544 KB Output is correct
17 Correct 715 ms 150108 KB Output is correct
18 Correct 18 ms 36308 KB Output is correct
19 Correct 17 ms 36308 KB Output is correct
20 Correct 18 ms 36392 KB Output is correct
21 Correct 17 ms 36376 KB Output is correct
22 Correct 18 ms 36436 KB Output is correct
23 Correct 17 ms 36312 KB Output is correct
24 Incorrect 2355 ms 193808 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36308 KB Output is correct
2 Correct 3103 ms 230836 KB Output is correct
3 Correct 2041 ms 226376 KB Output is correct
4 Correct 2603 ms 228656 KB Output is correct
5 Correct 2084 ms 190472 KB Output is correct
6 Correct 1710 ms 173012 KB Output is correct
7 Correct 1518 ms 167012 KB Output is correct
8 Correct 559 ms 130496 KB Output is correct
9 Correct 3084 ms 227596 KB Output is correct
10 Correct 2065 ms 229680 KB Output is correct
11 Correct 2384 ms 192132 KB Output is correct
12 Correct 1824 ms 192852 KB Output is correct
13 Correct 1245 ms 181908 KB Output is correct
14 Correct 1310 ms 186260 KB Output is correct
15 Correct 18 ms 36308 KB Output is correct
16 Correct 17 ms 36352 KB Output is correct
17 Correct 17 ms 36344 KB Output is correct
18 Correct 17 ms 36396 KB Output is correct
19 Correct 17 ms 36432 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 36332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 36308 KB Output isn't correct
2 Halted 0 ms 0 KB -