oj.uz

답안 #561247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561247 2022-05-12T14:05:54 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 110668 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];
int deep[N];

void dfs_euler(int u, int d = 0, int p = -1) {
	deep[u] = 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);
			deep[u] = max(deep[u], deep[v]);
			sp[0][timer++] = {d, u};
		}
	}
	sort(all(g[u]), [](auto x, auto y) {
		return deep[x] > deep[y];
	});
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10496 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 8 ms 10848 KB Output is correct
5 Incorrect 9 ms 10904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 667 ms 88240 KB Output is correct
3 Correct 2502 ms 84468 KB Output is correct
4 Correct 684 ms 100916 KB Output is correct
5 Correct 1267 ms 86116 KB Output is correct
6 Correct 2065 ms 86496 KB Output is correct
7 Correct 2059 ms 86496 KB Output is correct
8 Correct 1720 ms 89200 KB Output is correct
9 Correct 498 ms 110668 KB Output is correct
10 Correct 774 ms 105060 KB Output is correct
11 Correct 693 ms 87500 KB Output is correct
12 Correct 2251 ms 84312 KB Output is correct
13 Correct 877 ms 86348 KB Output is correct
14 Correct 1290 ms 85496 KB Output is correct
15 Correct 1809 ms 85104 KB Output is correct
16 Correct 2145 ms 84880 KB Output is correct
17 Correct 2555 ms 85024 KB Output is correct
18 Correct 9 ms 10452 KB Output is correct
19 Correct 8 ms 10580 KB Output is correct
20 Correct 6 ms 10580 KB Output is correct
21 Correct 7 ms 10476 KB Output is correct
22 Correct 7 ms 10580 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 667 ms 88240 KB Output is correct
3 Correct 2502 ms 84468 KB Output is correct
4 Correct 684 ms 100916 KB Output is correct
5 Correct 1267 ms 86116 KB Output is correct
6 Correct 2065 ms 86496 KB Output is correct
7 Correct 2059 ms 86496 KB Output is correct
8 Correct 1720 ms 89200 KB Output is correct
9 Correct 498 ms 110668 KB Output is correct
10 Correct 774 ms 105060 KB Output is correct
11 Correct 693 ms 87500 KB Output is correct
12 Correct 2251 ms 84312 KB Output is correct
13 Correct 877 ms 86348 KB Output is correct
14 Correct 1290 ms 85496 KB Output is correct
15 Correct 1809 ms 85104 KB Output is correct
16 Correct 2145 ms 84880 KB Output is correct
17 Correct 2555 ms 85024 KB Output is correct
18 Correct 9 ms 10452 KB Output is correct
19 Correct 8 ms 10580 KB Output is correct
20 Correct 6 ms 10580 KB Output is correct
21 Correct 7 ms 10476 KB Output is correct
22 Correct 7 ms 10580 KB Output is correct
23 Correct 7 ms 10500 KB Output is correct
24 Incorrect 784 ms 87248 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10452 KB Output is correct
2 Correct 1262 ms 107244 KB Output is correct
3 Execution timed out 4081 ms 100652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 1244 ms 101760 KB Output is correct
3 Execution timed out 4101 ms 95056 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10496 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 8 ms 10848 KB Output is correct
5 Incorrect 9 ms 10904 KB Output isn't correct
6 Halted 0 ms 0 KB -