oj.uz

Submission #561264

# Submission time Handle Problem Language Result Execution time Memory
561264 2022-05-12T14:27:45 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
12 / 100
 4000 ms 98516 KB 
//bs:sanitizers
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

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

int n, modulo;

vector<int> g[N];
int ipow[EULER], depth[N];
pair<int, int> sp[LOG][EULER];
int order[N], timer = 0, parent[N];

void dfs_euler(int u, int d = 0, int p = -1) {
	order[u] = timer;
	parent[u] = p;
	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<int> layer[N];
pair<int, int> inv[N];
int layer_start[N];
int lnk[N];

ll t[2 * N];

int get(int u) {
	auto [x, y] = inv[u];
	return layer_start[x] + y;
}

void upd(int l, int r, int w) {
	l += n;
	r += n;
	while (l <= r) {
		if (l & 1)	(t[l] *= w) %= modulo;
		if (!(r & 1))	(t[r] *= w) %= modulo;
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	n = read_int(), modulo = read_int();
	fill(t, t + 2 * n, 1);
	for (int i = 1; i < n; ++i) {
		int u, v;
		u = read_int(), v = read_int();
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	
	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;
	}

	queue<tuple<int, int, int>> bfs;
	bfs.push({0, -1, 0});
	layer[0].push_back(0);
	while (sz(bfs)) {
		auto [u, p, dst] = bfs.front();
		bfs.pop();
		lnk[u] = sz(layer[dst + 1]);
		for (int v : g[u]) {
			if (v != p) {
				bfs.push({v, u, dst + 1});
				inv[v] = {dst + 1, sz(layer[dst + 1])};
				layer[dst + 1].push_back(v);
			}
		}
	}
	for (int i = 1; i < N; ++i) {
		layer_start[i] = layer_start[i - 1] + sz(layer[i - 1]);
	}

	for (int i = 0; i < n; ++i) {
		int x = read_int();
		t[get(i) + n] = x;
	}

	int queries = read_int();
	while (queries--) {
		int type = read_int();
		if (type == 1) {
			int x = read_int(), d = read_int(), w = read_int();
			--x;

			auto upd_with_base = [&](int where, int index) {
				int lef = -1, rig = index;
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						rig = mid;
					} else {
						lef = mid;
					}
				}
				bool flag = (rig != index);
				upd(layer_start[where] + rig, layer_start[where] + index - 1, w);
			
				lef = index - 1, rig = sz(layer[where]);
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						lef = mid;
					} else {
						rig = mid;
					}
				}
				flag |= index - 1 != lef;
				upd(layer_start[where] + index, layer_start[where] + lef, w);
				return flag;
			};

			for (int u = parent[x]; u != -1; u = parent[u]) {
				if (!upd_with_base(inv[u].x, inv[u].y)) {
					break;
				}
			}
			int where = inv[x].x, index = inv[x].y;
			while (1) {
				// cout << where << " " << index << endl;
				// cout << layer[where][index] << endl;
				if (!upd_with_base(where, index)) {
					break;
				}
				if (index == sz(layer[where])) {
					++where;
					index = sz(layer[where]);
				} else {
					index = lnk[layer[where][index]];
					++where;
				}
			}
		} else {
			int x = read_int();
			int i = get(x - 1) + n;
			ll res = 1;
			while (i) {
				(res *= t[i]) %= modulo;
				i /= 2;
			}
			write_int(res);
			write_char('\n');
			// cout << res << "\n";
		}
		// for (int j = 0; j < n; ++j) {
		// 	int i = get(j) + n;
		// 	ll res = 1;
		// 	while (i) {
		// 		(res *= t[i]) %= modulo;
		// 		i /= 2;
		// 	}
		// 	cout << res << " ";
		// }
		// cout << endl;
	}
	wflush();
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10580 KB Output is correct
2 Correct 7 ms 10580 KB Output is correct
3 Correct 7 ms 10580 KB Output is correct
4 Correct 8 ms 10836 KB Output is correct
5 Correct 9 ms 10836 KB Output is correct
6 Correct 10 ms 10900 KB Output is correct
7 Correct 9 ms 10828 KB Output is correct
8 Correct 7 ms 10836 KB Output is correct
9 Correct 9 ms 10524 KB Output is correct
10 Correct 8 ms 10580 KB Output is correct
11 Correct 7 ms 10520 KB Output is correct
12 Correct 7 ms 10580 KB Output is correct
13 Correct 8 ms 10580 KB Output is correct
14 Correct 8 ms 10468 KB Output is correct
15 Correct 7 ms 10504 KB Output is correct
16 Correct 7 ms 10516 KB Output is correct
17 Correct 7 ms 10520 KB Output is correct
18 Correct 8 ms 10512 KB Output is correct
19 Correct 8 ms 10556 KB Output is correct
20 Correct 9 ms 10492 KB Output is correct
21 Correct 7 ms 10580 KB Output is correct
22 Correct 8 ms 10580 KB Output is correct
23 Correct 7 ms 10580 KB Output is correct
24 Correct 7 ms 10548 KB Output is correct
25 Correct 7 ms 10552 KB Output is correct
26 Correct 7 ms 10512 KB Output is correct
27 Correct 7 ms 10580 KB Output is correct
28 Correct 7 ms 10600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10524 KB Output is correct
2 Correct 662 ms 87528 KB Output is correct
3 Correct 3245 ms 84304 KB Output is correct
4 Correct 501 ms 92936 KB Output is correct
5 Correct 1782 ms 86228 KB Output is correct
6 Correct 3416 ms 86216 KB Output is correct
7 Correct 3420 ms 86544 KB Output is correct
8 Correct 1487 ms 88880 KB Output is correct
9 Correct 420 ms 98516 KB Output is correct
10 Correct 530 ms 93948 KB Output is correct
11 Correct 650 ms 87548 KB Output is correct
12 Correct 3057 ms 84608 KB Output is correct
13 Correct 944 ms 86560 KB Output is correct
14 Correct 1619 ms 85720 KB Output is correct
15 Correct 2383 ms 84904 KB Output is correct
16 Correct 2995 ms 85292 KB Output is correct
17 Correct 3615 ms 85676 KB Output is correct
18 Correct 7 ms 10580 KB Output is correct
19 Correct 9 ms 10600 KB Output is correct
20 Correct 7 ms 10600 KB Output is correct
21 Correct 8 ms 10540 KB Output is correct
22 Correct 7 ms 10532 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10524 KB Output is correct
2 Correct 662 ms 87528 KB Output is correct
3 Correct 3245 ms 84304 KB Output is correct
4 Correct 501 ms 92936 KB Output is correct
5 Correct 1782 ms 86228 KB Output is correct
6 Correct 3416 ms 86216 KB Output is correct
7 Correct 3420 ms 86544 KB Output is correct
8 Correct 1487 ms 88880 KB Output is correct
9 Correct 420 ms 98516 KB Output is correct
10 Correct 530 ms 93948 KB Output is correct
11 Correct 650 ms 87548 KB Output is correct
12 Correct 3057 ms 84608 KB Output is correct
13 Correct 944 ms 86560 KB Output is correct
14 Correct 1619 ms 85720 KB Output is correct
15 Correct 2383 ms 84904 KB Output is correct
16 Correct 2995 ms 85292 KB Output is correct
17 Correct 3615 ms 85676 KB Output is correct
18 Correct 7 ms 10580 KB Output is correct
19 Correct 9 ms 10600 KB Output is correct
20 Correct 7 ms 10600 KB Output is correct
21 Correct 8 ms 10540 KB Output is correct
22 Correct 7 ms 10532 KB Output is correct
23 Correct 9 ms 10512 KB Output is correct
24 Correct 781 ms 87532 KB Output is correct
25 Execution timed out 4008 ms 84100 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10580 KB Output is correct
2 Correct 796 ms 95464 KB Output is correct
3 Execution timed out 4041 ms 93100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10624 KB Output is correct
2 Correct 1090 ms 94792 KB Output is correct
3 Execution timed out 4053 ms 91284 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10580 KB Output is correct
2 Correct 7 ms 10580 KB Output is correct
3 Correct 7 ms 10580 KB Output is correct
4 Correct 8 ms 10836 KB Output is correct
5 Correct 9 ms 10836 KB Output is correct
6 Correct 10 ms 10900 KB Output is correct
7 Correct 9 ms 10828 KB Output is correct
8 Correct 7 ms 10836 KB Output is correct
9 Correct 9 ms 10524 KB Output is correct
10 Correct 8 ms 10580 KB Output is correct
11 Correct 7 ms 10520 KB Output is correct
12 Correct 7 ms 10580 KB Output is correct
13 Correct 8 ms 10580 KB Output is correct
14 Correct 8 ms 10468 KB Output is correct
15 Correct 7 ms 10504 KB Output is correct
16 Correct 7 ms 10516 KB Output is correct
17 Correct 7 ms 10520 KB Output is correct
18 Correct 8 ms 10512 KB Output is correct
19 Correct 8 ms 10556 KB Output is correct
20 Correct 9 ms 10492 KB Output is correct
21 Correct 7 ms 10580 KB Output is correct
22 Correct 8 ms 10580 KB Output is correct
23 Correct 7 ms 10580 KB Output is correct
24 Correct 7 ms 10548 KB Output is correct
25 Correct 7 ms 10552 KB Output is correct
26 Correct 7 ms 10512 KB Output is correct
27 Correct 7 ms 10580 KB Output is correct
28 Correct 7 ms 10600 KB Output is correct
29 Correct 7 ms 10524 KB Output is correct
30 Correct 662 ms 87528 KB Output is correct
31 Correct 3245 ms 84304 KB Output is correct
32 Correct 501 ms 92936 KB Output is correct
33 Correct 1782 ms 86228 KB Output is correct
34 Correct 3416 ms 86216 KB Output is correct
35 Correct 3420 ms 86544 KB Output is correct
36 Correct 1487 ms 88880 KB Output is correct
37 Correct 420 ms 98516 KB Output is correct
38 Correct 530 ms 93948 KB Output is correct
39 Correct 650 ms 87548 KB Output is correct
40 Correct 3057 ms 84608 KB Output is correct
41 Correct 944 ms 86560 KB Output is correct
42 Correct 1619 ms 85720 KB Output is correct
43 Correct 2383 ms 84904 KB Output is correct
44 Correct 2995 ms 85292 KB Output is correct
45 Correct 3615 ms 85676 KB Output is correct
46 Correct 7 ms 10580 KB Output is correct
47 Correct 9 ms 10600 KB Output is correct
48 Correct 7 ms 10600 KB Output is correct
49 Correct 8 ms 10540 KB Output is correct
50 Correct 7 ms 10532 KB Output is correct
51 Correct 9 ms 10512 KB Output is correct
52 Correct 781 ms 87532 KB Output is correct
53 Execution timed out 4008 ms 84100 KB Time limit exceeded
54 Halted 0 ms 0 KB -