oj.uz

Submission #558552

# Submission time Handle Problem Language Result Execution time Memory
558552 2022-05-07T14:08:56 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
21 / 100
 3512 ms 302852 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;
const int BUFF = 4096;

char buff[BUFF + 1];
int buff_it = 0, buff_len = 0;

char wbuff[BUFF];
int wbuff_len = 0;

char read_char() {
	if (buff_it == buff_len) {
		buff_len = (int) fread(buff, 1, BUFF, stdin);
		buff[buff_len] = 0;
		buff_it = 0;
	}
	return buff[buff_it++];
}

int read_int() {
	char c = ' ';
	while (!isdigit(c = read_char()));
	int res = 0;
	do {
		res *= 10;
		res += c - '0';
	} while (isdigit(c = read_char()));
	return res;
}

void wflush() {
	fwrite(wbuff, 1, wbuff_len, stdout);
	wbuff_len = 0;
}

void write_char(char c) {
	if (wbuff_len == BUFF) {
		wflush();
	}
	wbuff[wbuff_len++] = c;
}

void write_int(ll x) {
	static char cbuff[20];
	int i = 0;
	if (!x) {
		write_char('0');
		return;
	}
	for (; x; x /= 10) {
		cbuff[i++] = char(x % 10 + '0');
	}
	for (; i--; ) {
		write_char(cbuff[i]);
	}
}

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

struct CentroidNode {
	int parent, depth, sz;
	vector<int> ob, pb;
	int *op[DIFF], *pp[DIFF];
	ll *oi, *pi;
} tc[N];

const int INT_MEM = 136806840, LL_MEM = 15200760;

int int_mem[INT_MEM];
ll ll_mem[LL_MEM];
int next_free = 0, ll_free = 0;

int *allocate(int x) {
	int *res = int_mem + next_free;
	next_free += x;
	assert(next_free < INT_MEM);
	return res;
}

ll *allocatell(int x) {
	ll *res = ll_mem + ll_free;
	ll_free += x;
	assert(ll_free < LL_MEM);
	return res;
}

int where[LOG][N], where2[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;

queue<tuple<int, int, int>> bfs;

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;
	}

	bfs.push({1, root, -1});
	int prev = -1, at = 0;
	node.pb.push_back(0);
	while (sz(bfs)) {
		auto [d, u, p] = bfs.front();
		bfs.pop();
		where2[depth][u] = at;
		if (prev != d) {
			node.pb.push_back(at);
			prev = d;
		}
		++at;
		for (int v : g[u]) {
			if (!used[v] && v != p) {
				bfs.push({d + 1, v, u});
			}
		}
	}

	bfs.push({0, centroid, -1});
	prev = -1, at = 0;
	while (sz(bfs)) {
		auto [d, u, p] = bfs.front();
		bfs.pop();
		where[depth][u] = at;
		if (prev != d) {
			node.ob.push_back(at);
			prev = d;
		}
		++at;
		for (int v : g[u]) {
			if (!used[v] && v != p) {
				bfs.push({d + 1, v, u});
			}
		}
	}
	
	for (int i = 0; i < DIFF; ++i) {
		node.op[i] = allocate(node.sz);
		node.pp[i] = allocate(node.sz);
	}
	node.oi = allocatell(node.sz);
	node.pi = allocatell(node.sz);

	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, int r, int, T func) {
	for (; r >= 0; r &= r + 1, --r) {
		func(r);
	}
}

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.ob) ? node.sz : node.ob[dst + 1]);

	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];
		});
	}
	if (ineq != 1) {
		tdo(0, bound - 1, node.sz, [&](int j) {
			(node.oi[j] *= ineq) %= l;
		});
	}

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

	dst = d - dist(node.parent, x);
	bound = dst < 0 ? 0 : (dst + 1 >= sz(node.pb) ? node.sz : node.pb[dst + 1]);
	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];
	for (; i < node.sz; i |= i + 1) {
		for (int j = 0; j < diff; ++j) {
			part[j] += node.op[j][i];
		}
		(ineq *= node.oi[i]) %= l;
	}

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

	i = where2[node.depth][x];
	for (; i < node.sz; i |= i + 1) {
		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() {
#ifdef DEBUG
	freopen("output.txt", "w", stdout);
#endif
	int n = read_int();
	l = read_int();
	fill(all(ll_mem), 1);
	for (int i = 1; i < n; ++i) {
		int u = read_int(), v = read_int();
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	for (int i = 0; i < n; ++i) {
		h[i] = read_int();
	}
	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 = read_int();
	auto fact = factor(int(l));
	diff = sz(fact);

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

	while (queries--) {
		int type = read_int();
		if (type == 1) {
			int x = read_int(), d = read_int(), w = read_int();
			--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 = read_int() - 1;
			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;
			write_int((h[x] * res) % l);
			write_char('\n');
			// for (int u : part) {
			// 	cout << u << " ";
			// }
			// cout << ineq << "\n";
		}
	}
	wflush();
	cerr << clock() << endl;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 142756 KB Output is correct
2 Correct 66 ms 142796 KB Output is correct
3 Correct 62 ms 142848 KB Output is correct
4 Incorrect 76 ms 143448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142780 KB Output is correct
2 Correct 2526 ms 254608 KB Output is correct
3 Correct 1737 ms 250744 KB Output is correct
4 Correct 3007 ms 283428 KB Output is correct
5 Correct 2160 ms 252204 KB Output is correct
6 Correct 1600 ms 246820 KB Output is correct
7 Correct 1441 ms 245124 KB Output is correct
8 Correct 510 ms 227944 KB Output is correct
9 Correct 3443 ms 290120 KB Output is correct
10 Correct 2418 ms 285728 KB Output is correct
11 Correct 2512 ms 254032 KB Output is correct
12 Correct 1752 ms 250652 KB Output is correct
13 Correct 437 ms 229100 KB Output is correct
14 Correct 474 ms 230484 KB Output is correct
15 Correct 590 ms 232692 KB Output is correct
16 Correct 646 ms 234304 KB Output is correct
17 Correct 692 ms 236456 KB Output is correct
18 Correct 64 ms 142848 KB Output is correct
19 Correct 63 ms 142856 KB Output is correct
20 Correct 64 ms 142796 KB Output is correct
21 Correct 67 ms 142920 KB Output is correct
22 Correct 61 ms 142896 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142780 KB Output is correct
2 Correct 2526 ms 254608 KB Output is correct
3 Correct 1737 ms 250744 KB Output is correct
4 Correct 3007 ms 283428 KB Output is correct
5 Correct 2160 ms 252204 KB Output is correct
6 Correct 1600 ms 246820 KB Output is correct
7 Correct 1441 ms 245124 KB Output is correct
8 Correct 510 ms 227944 KB Output is correct
9 Correct 3443 ms 290120 KB Output is correct
10 Correct 2418 ms 285728 KB Output is correct
11 Correct 2512 ms 254032 KB Output is correct
12 Correct 1752 ms 250652 KB Output is correct
13 Correct 437 ms 229100 KB Output is correct
14 Correct 474 ms 230484 KB Output is correct
15 Correct 590 ms 232692 KB Output is correct
16 Correct 646 ms 234304 KB Output is correct
17 Correct 692 ms 236456 KB Output is correct
18 Correct 64 ms 142848 KB Output is correct
19 Correct 63 ms 142856 KB Output is correct
20 Correct 64 ms 142796 KB Output is correct
21 Correct 67 ms 142920 KB Output is correct
22 Correct 61 ms 142896 KB Output is correct
23 Correct 62 ms 142784 KB Output is correct
24 Incorrect 2591 ms 254372 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 64 ms 142768 KB Output is correct
2 Correct 3512 ms 302852 KB Output is correct
3 Correct 2531 ms 298264 KB Output is correct
4 Correct 3004 ms 299368 KB Output is correct
5 Correct 2234 ms 263628 KB Output is correct
6 Correct 1726 ms 257832 KB Output is correct
7 Correct 1462 ms 254500 KB Output is correct
8 Correct 447 ms 227856 KB Output is correct
9 Correct 3287 ms 298636 KB Output is correct
10 Correct 2447 ms 300788 KB Output is correct
11 Correct 2457 ms 264716 KB Output is correct
12 Correct 1921 ms 263864 KB Output is correct
13 Correct 1249 ms 250864 KB Output is correct
14 Correct 1263 ms 253132 KB Output is correct
15 Correct 80 ms 142796 KB Output is correct
16 Correct 63 ms 142796 KB Output is correct
17 Correct 62 ms 142800 KB Output is correct
18 Correct 63 ms 142816 KB Output is correct
19 Correct 62 ms 142784 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142756 KB Output is correct
2 Incorrect 3302 ms 284408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 142756 KB Output is correct
2 Correct 66 ms 142796 KB Output is correct
3 Correct 62 ms 142848 KB Output is correct
4 Incorrect 76 ms 143448 KB Output isn't correct
5 Halted 0 ms 0 KB -