oj.uz

Submission #561245

# Submission time Handle Problem Language Result Execution time Memory
561245 2022-05-12T14:01:38 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 113768 KB 
//bs:sanitizers
#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;

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

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);
	cin >> n >> modulo;
	fill(t, t + 2 * n, 1);
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		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});
	while (sz(bfs)) {
		auto [u, p, dst] = bfs.front();
		bfs.pop();
		inv[u] = {dst, sz(layer[dst])};
		layer[dst].push_back(u);
		for (int v : g[u]) {
			if (v != p) {
				bfs.push({v, u, dst + 1});
			}
		}
	}
	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;
		cin >> x;
		t[get(i) + n] = x;
	}

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

			auto upd_with_base = [&](int u) {
				int where = inv[u].x;
				int lef = -1, rig = inv[u].y;
				while (rig - lef > 1) {
					int mid = (lef + rig) / 2;
					if (dist(layer[where][mid], x) <= d) {
						rig = mid;
					} else {
						lef = mid;
					}
				}
				upd(get(layer[where][rig]), get(u), w);
			
				lef = inv[u].y, 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;
					}
				}
				upd(get(u) + 1, get(layer[where][lef]), w);
			};

			for (int u = parent[x]; u != -1; u = parent[u]) {
				// cout << "top" << u << endl;
				if (dist(x, u) > d) {
					break;
				}
				upd_with_base(u);
			}
			for (int u = x; u != -1; ) {
				// cout << "bottom" << u << endl;
				if (dist(x, u) > d) {
					break;
				}
				upd_with_base(u);
				
				int q = -1;
				for (int v : g[u]) {
					if (v != parent[u]) {
						q = v;
						break;
					}
				}
				u = q;
			}
		} else {
			int x;
			cin >> x;
			int i = get(x - 1) + n;
			ll res = 1;
			while (i) {
				(res *= t[i]) %= modulo;
				i /= 2;
			}
			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;
	}
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 9 ms 10836 KB Output is correct
5 Incorrect 10 ms 10768 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10548 KB Output is correct
2 Correct 651 ms 93576 KB Output is correct
3 Correct 2616 ms 94040 KB Output is correct
4 Correct 691 ms 106392 KB Output is correct
5 Correct 1380 ms 93480 KB Output is correct
6 Correct 2187 ms 91192 KB Output is correct
7 Correct 2151 ms 93932 KB Output is correct
8 Correct 1803 ms 94324 KB Output is correct
9 Correct 523 ms 113768 KB Output is correct
10 Correct 822 ms 112084 KB Output is correct
11 Correct 753 ms 92076 KB Output is correct
12 Correct 2350 ms 90576 KB Output is correct
13 Correct 894 ms 96676 KB Output is correct
14 Correct 1412 ms 95576 KB Output is correct
15 Correct 1792 ms 85068 KB Output is correct
16 Correct 2217 ms 89092 KB Output is correct
17 Correct 2430 ms 90100 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 7 ms 10496 KB Output is correct
20 Correct 7 ms 10508 KB Output is correct
21 Correct 6 ms 10504 KB Output is correct
22 Correct 7 ms 10580 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10548 KB Output is correct
2 Correct 651 ms 93576 KB Output is correct
3 Correct 2616 ms 94040 KB Output is correct
4 Correct 691 ms 106392 KB Output is correct
5 Correct 1380 ms 93480 KB Output is correct
6 Correct 2187 ms 91192 KB Output is correct
7 Correct 2151 ms 93932 KB Output is correct
8 Correct 1803 ms 94324 KB Output is correct
9 Correct 523 ms 113768 KB Output is correct
10 Correct 822 ms 112084 KB Output is correct
11 Correct 753 ms 92076 KB Output is correct
12 Correct 2350 ms 90576 KB Output is correct
13 Correct 894 ms 96676 KB Output is correct
14 Correct 1412 ms 95576 KB Output is correct
15 Correct 1792 ms 85068 KB Output is correct
16 Correct 2217 ms 89092 KB Output is correct
17 Correct 2430 ms 90100 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 7 ms 10496 KB Output is correct
20 Correct 7 ms 10508 KB Output is correct
21 Correct 6 ms 10504 KB Output is correct
22 Correct 7 ms 10580 KB Output is correct
23 Correct 7 ms 10452 KB Output is correct
24 Incorrect 749 ms 93616 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 1166 ms 109788 KB Output is correct
3 Execution timed out 4043 ms 103624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 1207 ms 105160 KB Output is correct
3 Execution timed out 4033 ms 99036 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 9 ms 10836 KB Output is correct
5 Incorrect 10 ms 10768 KB Output isn't correct
6 Halted 0 ms 0 KB -