oj.uz

Submission #558566

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

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

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

int next_free = 0;

Arr *allocate(int x) {
	Arr *res = int_mem + next_free;
	next_free += x;
	assert(next_free < INT_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);

	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]);

	if (ineq != 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];
			}
			(node.op[j].i *= ineq) %= l;
		});
	} else {
		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 (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]);
	if (inv != 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];
			}
			(node.pp[j].i *= inv) %= l;
		});
	} else {
		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];
			}
		});
	}
}

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.op[i].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.pp[i].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();
	for (int i = 0; i < INT_MEM; ++i) {
		int_mem[i].i = 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 164 ms 437328 KB Output is correct
2 Correct 165 ms 437200 KB Output is correct
3 Correct 170 ms 437104 KB Output is correct
4 Correct 169 ms 437724 KB Output is correct
5 Correct 166 ms 437708 KB Output is correct
6 Correct 173 ms 437676 KB Output is correct
7 Correct 166 ms 437568 KB Output is correct
8 Correct 166 ms 437564 KB Output is correct
9 Correct 170 ms 437164 KB Output is correct
10 Correct 162 ms 437156 KB Output is correct
11 Correct 162 ms 437144 KB Output is correct
12 Correct 171 ms 437244 KB Output is correct
13 Correct 175 ms 437196 KB Output is correct
14 Correct 176 ms 437172 KB Output is correct
15 Correct 167 ms 437176 KB Output is correct
16 Correct 174 ms 437136 KB Output is correct
17 Correct 162 ms 437196 KB Output is correct
18 Correct 163 ms 437120 KB Output is correct
19 Correct 164 ms 437256 KB Output is correct
20 Correct 170 ms 437192 KB Output is correct
21 Correct 172 ms 437196 KB Output is correct
22 Correct 160 ms 437180 KB Output is correct
23 Correct 165 ms 437200 KB Output is correct
24 Correct 165 ms 437172 KB Output is correct
25 Correct 174 ms 437188 KB Output is correct
26 Correct 164 ms 437184 KB Output is correct
27 Correct 170 ms 437136 KB Output is correct
28 Correct 168 ms 437224 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 437196 KB Output is correct
2 Execution timed out 4100 ms 548400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 437196 KB Output is correct
2 Execution timed out 4100 ms 548400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 437204 KB Output is correct
2 Execution timed out 4070 ms 581196 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 437280 KB Output is correct
2 Execution timed out 4078 ms 577176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 437328 KB Output is correct
2 Correct 165 ms 437200 KB Output is correct
3 Correct 170 ms 437104 KB Output is correct
4 Correct 169 ms 437724 KB Output is correct
5 Correct 166 ms 437708 KB Output is correct
6 Correct 173 ms 437676 KB Output is correct
7 Correct 166 ms 437568 KB Output is correct
8 Correct 166 ms 437564 KB Output is correct
9 Correct 170 ms 437164 KB Output is correct
10 Correct 162 ms 437156 KB Output is correct
11 Correct 162 ms 437144 KB Output is correct
12 Correct 171 ms 437244 KB Output is correct
13 Correct 175 ms 437196 KB Output is correct
14 Correct 176 ms 437172 KB Output is correct
15 Correct 167 ms 437176 KB Output is correct
16 Correct 174 ms 437136 KB Output is correct
17 Correct 162 ms 437196 KB Output is correct
18 Correct 163 ms 437120 KB Output is correct
19 Correct 164 ms 437256 KB Output is correct
20 Correct 170 ms 437192 KB Output is correct
21 Correct 172 ms 437196 KB Output is correct
22 Correct 160 ms 437180 KB Output is correct
23 Correct 165 ms 437200 KB Output is correct
24 Correct 165 ms 437172 KB Output is correct
25 Correct 174 ms 437188 KB Output is correct
26 Correct 164 ms 437184 KB Output is correct
27 Correct 170 ms 437136 KB Output is correct
28 Correct 168 ms 437224 KB Output is correct
29 Correct 172 ms 437196 KB Output is correct
30 Execution timed out 4100 ms 548400 KB Time limit exceeded
31 Halted 0 ms 0 KB -