oj.uz

Submission #558553

# Submission time Handle Problem Language Result Execution time Memory
558553 2022-05-07T14:10:28 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
51 / 100
 3558 ms 304592 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 = {{2, 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 68 ms 142916 KB Output is correct
2 Correct 65 ms 142872 KB Output is correct
3 Correct 66 ms 142884 KB Output is correct
4 Incorrect 63 ms 143408 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 142824 KB Output is correct
2 Correct 2657 ms 264008 KB Output is correct
3 Correct 1810 ms 261148 KB Output is correct
4 Correct 2978 ms 296120 KB Output is correct
5 Correct 2217 ms 262512 KB Output is correct
6 Correct 1691 ms 255048 KB Output is correct
7 Correct 1484 ms 252292 KB Output is correct
8 Correct 532 ms 229456 KB Output is correct
9 Correct 3488 ms 302104 KB Output is correct
10 Correct 2421 ms 299476 KB Output is correct
11 Correct 2508 ms 263568 KB Output is correct
12 Correct 1969 ms 261324 KB Output is correct
13 Correct 513 ms 230808 KB Output is correct
14 Correct 531 ms 232100 KB Output is correct
15 Correct 643 ms 234512 KB Output is correct
16 Correct 640 ms 236384 KB Output is correct
17 Correct 747 ms 238788 KB Output is correct
18 Correct 68 ms 142868 KB Output is correct
19 Correct 70 ms 142872 KB Output is correct
20 Correct 67 ms 142904 KB Output is correct
21 Correct 68 ms 142852 KB Output is correct
22 Correct 62 ms 142796 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142824 KB Output is correct
2 Correct 2657 ms 264008 KB Output is correct
3 Correct 1810 ms 261148 KB Output is correct
4 Correct 2978 ms 296120 KB Output is correct
5 Correct 2217 ms 262512 KB Output is correct
6 Correct 1691 ms 255048 KB Output is correct
7 Correct 1484 ms 252292 KB Output is correct
8 Correct 532 ms 229456 KB Output is correct
9 Correct 3488 ms 302104 KB Output is correct
10 Correct 2421 ms 299476 KB Output is correct
11 Correct 2508 ms 263568 KB Output is correct
12 Correct 1969 ms 261324 KB Output is correct
13 Correct 513 ms 230808 KB Output is correct
14 Correct 531 ms 232100 KB Output is correct
15 Correct 643 ms 234512 KB Output is correct
16 Correct 640 ms 236384 KB Output is correct
17 Correct 747 ms 238788 KB Output is correct
18 Correct 68 ms 142868 KB Output is correct
19 Correct 70 ms 142872 KB Output is correct
20 Correct 67 ms 142904 KB Output is correct
21 Correct 68 ms 142852 KB Output is correct
22 Correct 62 ms 142796 KB Output is correct
23 Correct 63 ms 142868 KB Output is correct
24 Incorrect 2668 ms 264772 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 65 ms 142876 KB Output is correct
2 Correct 3523 ms 302948 KB Output is correct
3 Correct 2828 ms 298368 KB Output is correct
4 Correct 3156 ms 299548 KB Output is correct
5 Correct 2336 ms 250844 KB Output is correct
6 Correct 1809 ms 245164 KB Output is correct
7 Correct 1541 ms 243984 KB Output is correct
8 Correct 436 ms 226216 KB Output is correct
9 Correct 3426 ms 298476 KB Output is correct
10 Correct 2779 ms 300976 KB Output is correct
11 Correct 2480 ms 251736 KB Output is correct
12 Correct 2052 ms 250996 KB Output is correct
13 Correct 1453 ms 250936 KB Output is correct
14 Correct 1476 ms 242444 KB Output is correct
15 Correct 69 ms 142808 KB Output is correct
16 Correct 62 ms 142856 KB Output is correct
17 Correct 61 ms 142804 KB Output is correct
18 Correct 79 ms 142796 KB Output is correct
19 Correct 67 ms 142836 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 142796 KB Output is correct
2 Correct 3558 ms 300524 KB Output is correct
3 Correct 2841 ms 294832 KB Output is correct
4 Correct 3190 ms 297808 KB Output is correct
5 Correct 2461 ms 265096 KB Output is correct
6 Correct 1900 ms 260928 KB Output is correct
7 Correct 1627 ms 256720 KB Output is correct
8 Correct 493 ms 229176 KB Output is correct
9 Correct 3512 ms 304592 KB Output is correct
10 Correct 2710 ms 301752 KB Output is correct
11 Correct 2591 ms 266868 KB Output is correct
12 Correct 1999 ms 262820 KB Output is correct
13 Correct 1366 ms 251004 KB Output is correct
14 Correct 1389 ms 253300 KB Output is correct
15 Correct 66 ms 142804 KB Output is correct
16 Correct 75 ms 142848 KB Output is correct
17 Correct 67 ms 142848 KB Output is correct
18 Correct 74 ms 142844 KB Output is correct
19 Correct 65 ms 142824 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 142916 KB Output is correct
2 Correct 65 ms 142872 KB Output is correct
3 Correct 66 ms 142884 KB Output is correct
4 Incorrect 63 ms 143408 KB Output isn't correct
5 Halted 0 ms 0 KB -