oj.uz

Submission #558561

# Submission time Handle Problem Language Result Execution time Memory
558561 2022-05-07T14:25:20 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 413228 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;
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];

const int INT_MEM = 7600380, LL_MEM = 15200760;

__attribute__((aligned(16))) struct Arr {
	int a[12];
} int_mem[INT_MEM];

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

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

Arr *allocate(int x) {
	Arr *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});
			}
		}
	}
	
	node.op = allocate(node.sz);
	node.pp = 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);
	}
}

int part[12] __attribute__((aligned(16)));

void apply_for(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]);

	tdo(0, bound - 1, node.sz, [&](int j) {
#pragma GCC ivdep
		for (int i = 0; i < 9; ++i) {
			node.op[j].a[i] += 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]);
	tdo(0, bound - 1, node.sz, [&](int j) {
#pragma GCC ivdep
		for (int i = 0; i < 9; ++i) {
			node.pp[j].a[i] -= 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(ll &ineq, int u, int x) {
	const auto &node = tc[u];

	int i = where[node.depth][x];
	for (; i < node.sz; i |= i + 1) {
#pragma GCC ivdep
		for (int j = 0; j < 9; ++j) {
			part[j] += node.op[i].a[j];
		}
		(ineq *= node.oi[i]) %= l;
	}

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

	i = where2[node.depth][x];
	for (; i < node.sz; i |= i + 1) {
#pragma GCC ivdep
		for (int j = 0; j < 9; ++j) {
			part[j] += node.pp[i].a[j];
		}
		(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);

	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 [partr, ineq] = get_pw(w, fact);
			fill(all(part), 0);
			copy_n(begin(partr), sz(partr), begin(part));
			ll inv, tmp;
			exgcd(ineq, int(l), inv, tmp);
			inv = (inv % l + l) % l;

			int curr = x;
			while (curr != -1) {
				apply_for(ineq, int(inv), curr, x, d);
				curr = tc[curr].parent;
			}
		} else {
			int x = read_int() - 1;
			fill(all(part), 0);
			ll ineq = 1;
			int curr = x;
			while (curr != -1) {
				count_for(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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142796 KB Output is correct
2 Correct 61 ms 142872 KB Output is correct
3 Correct 63 ms 142812 KB Output is correct
4 Correct 65 ms 144020 KB Output is correct
5 Correct 67 ms 143956 KB Output is correct
6 Correct 66 ms 143872 KB Output is correct
7 Correct 63 ms 143660 KB Output is correct
8 Correct 62 ms 143272 KB Output is correct
9 Correct 61 ms 142840 KB Output is correct
10 Correct 65 ms 142776 KB Output is correct
11 Correct 67 ms 142832 KB Output is correct
12 Correct 70 ms 142876 KB Output is correct
13 Correct 62 ms 142796 KB Output is correct
14 Correct 71 ms 142768 KB Output is correct
15 Correct 62 ms 142860 KB Output is correct
16 Correct 66 ms 142796 KB Output is correct
17 Correct 73 ms 142828 KB Output is correct
18 Correct 66 ms 142896 KB Output is correct
19 Correct 67 ms 142804 KB Output is correct
20 Correct 63 ms 142784 KB Output is correct
21 Correct 73 ms 142812 KB Output is correct
22 Correct 61 ms 142900 KB Output is correct
23 Correct 61 ms 142856 KB Output is correct
24 Correct 63 ms 142796 KB Output is correct
25 Correct 62 ms 142956 KB Output is correct
26 Correct 65 ms 142848 KB Output is correct
27 Correct 65 ms 142908 KB Output is correct
28 Correct 64 ms 142796 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 142796 KB Output is correct
2 Correct 3697 ms 324356 KB Output is correct
3 Correct 2012 ms 330944 KB Output is correct
4 Execution timed out 4083 ms 382992 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 142796 KB Output is correct
2 Correct 3697 ms 324356 KB Output is correct
3 Correct 2012 ms 330944 KB Output is correct
4 Execution timed out 4083 ms 382992 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142796 KB Output is correct
2 Execution timed out 4062 ms 413228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 142820 KB Output is correct
2 Execution timed out 4107 ms 409120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 142796 KB Output is correct
2 Correct 61 ms 142872 KB Output is correct
3 Correct 63 ms 142812 KB Output is correct
4 Correct 65 ms 144020 KB Output is correct
5 Correct 67 ms 143956 KB Output is correct
6 Correct 66 ms 143872 KB Output is correct
7 Correct 63 ms 143660 KB Output is correct
8 Correct 62 ms 143272 KB Output is correct
9 Correct 61 ms 142840 KB Output is correct
10 Correct 65 ms 142776 KB Output is correct
11 Correct 67 ms 142832 KB Output is correct
12 Correct 70 ms 142876 KB Output is correct
13 Correct 62 ms 142796 KB Output is correct
14 Correct 71 ms 142768 KB Output is correct
15 Correct 62 ms 142860 KB Output is correct
16 Correct 66 ms 142796 KB Output is correct
17 Correct 73 ms 142828 KB Output is correct
18 Correct 66 ms 142896 KB Output is correct
19 Correct 67 ms 142804 KB Output is correct
20 Correct 63 ms 142784 KB Output is correct
21 Correct 73 ms 142812 KB Output is correct
22 Correct 61 ms 142900 KB Output is correct
23 Correct 61 ms 142856 KB Output is correct
24 Correct 63 ms 142796 KB Output is correct
25 Correct 62 ms 142956 KB Output is correct
26 Correct 65 ms 142848 KB Output is correct
27 Correct 65 ms 142908 KB Output is correct
28 Correct 64 ms 142796 KB Output is correct
29 Correct 65 ms 142796 KB Output is correct
30 Correct 3697 ms 324356 KB Output is correct
31 Correct 2012 ms 330944 KB Output is correct
32 Execution timed out 4083 ms 382992 KB Time limit exceeded
33 Halted 0 ms 0 KB -