oj.uz

답안 #558490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558490 2022-05-07T13:08:56 Z DanShaders Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 246024 KB 
#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, DIFF = 1;

vector<int> g[N];
int h[N], sz[N];
char used[N];

struct CentroidNode {
	int parent, depth;
	vector<pair<int, int>> od, pd;
	vector<int> op[DIFF], pp[DIFF];
	vector<ll> oi, pi;
} tc[N];

int where[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;

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;
	if (parent == -1) {
		croot = centroid;
	}

	// normal_queue<tuple<int, int, int>> bfsp;
	// bfsp.push({1, root, -1});
	// while (sz(bfsp)) {
	// 	auto [d, u, p] = bfsp.top();
	// 	bfsp.pop();
	// 	node.pd.push_back({d, u});
	// 	for (int v : g[u]) {
	// 		if (!used[v] && v != p) {
	// 			bfsp.push({d + 1, v, u});
	// 		}
	// 	}
	// }
	normal_queue<tuple<int, int, int>> bfso;
	bfso.push({0, centroid, -1});
	while (sz(bfso)) {
		auto [d, u, p] = bfso.top();
		bfso.pop();
		where[depth][u] = sz(node.od);
		node.od.push_back({d, u});
		for (int v : g[u]) {
			if (!used[v] && v != p) {
				bfso.push({d + 1, v, u});
			}
		}
	}
	
	for (int i = 0; i < DIFF; ++i) {
		node.op[i].resize(2 * sz(node.od));
		// node.pp[i].resize(2 * sz(node.od));
	}
	node.oi.resize(2 * sz(node.od), 1);
	// node.pi.resize(2 * sz(node.od), 1);

	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 l, int r, int s, T func) {
	l += s;
	r += s;
	while (l <= r) {
		if (l & 1)	func(l);
		if (!(r & 1))	func(r);
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}

void apply_for(const vector<int> &part, int ineq, int inv, int u, int x, int d) {
	auto &node = tc[u];

	int dst = d - dist(u, x);
	int bound = int(lower_bound(all(node.od), pair{dst + 1, -1}) - begin(node.od));
	for (int i = 0; i < diff; ++i) {
		if (part[i] == 0) {
			continue;
		}
		tdo(0, bound - 1, sz(node.od), [&](int j) {
			node.op[i][j] += part[i];
		});
		// for (int j = 0; j < bound; ++j) {
		// 	node.op[i][j] += part[i];
		// }
	}
	if (ineq != 1) {
		tdo(0, bound - 1, sz(node.od), [&](int j) {
			(node.oi[j] *= ineq) %= l;
		});
		// for (int j = 0; j < bound; ++j) {
		// 	(node.oi[j] *= ineq) %= l;
		// }
	}

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

	// dst = d - dist(node.parent, x);
	// bound = int(lower_bound(all(node.pd), pair{dst + 1, -1}) - begin(node.pd));
	// for (int i = 0; i < diff; ++i) {
	// 	if (part[i] == 0) {
	// 		continue;
	// 	}
	// 	// for (int j = 0; j < bound; ++j) {
	// 	// 	node.pp[i][j] -= part[i];
	// 	// }
	// 	tdo(0, bound - 1, sz(node.od), [&](int j) {
	// 		node.pp[i][j] -= part[i];
	// 	});
	// }
	// if (inv != 1) {
	// 	// for (int j = 0; j < bound; ++j) {
	// 	// 	(node.pi[j] *= inv) %= l;
	// 	// }
	// 	tdo(0, bound - 1, sz(node.od), [&](int j) {
	// 		(node.pi[j] *= inv) %= l;
	// 	});
	// }
}

void count_for(vector<int> &part, ll &ineq, int u, int x) {
	const auto &node = tc[u];

	int i = where[node.depth][x];
	// int i = sz(node.od) - 1;
	i += sz(node.od);

	while (i) {
		for (int j = 0; j < diff; ++j) {
			part[j] += node.op[j][i];
		}
		(ineq *= node.oi[i]) %= l;
		i /= 2;
	}

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

	// i = int(lower_bound(all(node.pd), pair{dist(node.parent, x), x}) - begin(node.pd));
	// i += sz(node.od);

	// while (i) {
	// 	for (int j = 0; j < diff; ++j) {
	// 		part[j] += node.pp[j][i];
	// 	}
	// 	(ineq *= node.pi[i]) %= l;
	// 	i /= 2;
	// }
}

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
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n >> l;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	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;
	cin >> queries;
	auto fact = factor(int(l));
	diff = sz(fact);

	diff = 1;
	fact = {{l, 1}};

	while (queries--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			--x;
			if (!w) {
				w = int(l);
			}
			auto [part, ineq] = get_pw(w, fact);
			ll inv, tmp;
			exgcd(ineq, int(l), inv, tmp);
			inv = (inv % l + l) % l;

			int curr = x;
			while (curr != -1) {
				apply_for(part, ineq, int(inv), curr, x, d);
				curr = tc[curr].parent;
			}
		} else {
			int x;
			cin >> x;
			--x;
			vector<int> part(diff);
			ll ineq = 1;
			int curr = x;
			while (curr != -1) {
				count_for(part, 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;
			cout << (h[x] * res) % l << "\n";
			// for (int u : part) {
			// 	cout << u << " ";
			// }
			// cout << ineq << "\n";
		}
	}
	cerr << clock() << endl;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 34772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 34788 KB Output is correct
2 Correct 2631 ms 213332 KB Output is correct
3 Correct 2045 ms 208144 KB Output is correct
4 Correct 2875 ms 242348 KB Output is correct
5 Correct 2421 ms 209696 KB Output is correct
6 Correct 1852 ms 188900 KB Output is correct
7 Correct 1622 ms 179640 KB Output is correct
8 Correct 605 ms 131116 KB Output is correct
9 Correct 3191 ms 246024 KB Output is correct
10 Correct 2732 ms 242276 KB Output is correct
11 Correct 2962 ms 212680 KB Output is correct
12 Correct 2552 ms 208888 KB Output is correct
13 Correct 712 ms 132584 KB Output is correct
14 Correct 841 ms 137164 KB Output is correct
15 Correct 951 ms 143248 KB Output is correct
16 Correct 968 ms 148596 KB Output is correct
17 Correct 1110 ms 155852 KB Output is correct
18 Correct 22 ms 34760 KB Output is correct
19 Correct 21 ms 34772 KB Output is correct
20 Correct 26 ms 34780 KB Output is correct
21 Correct 21 ms 34788 KB Output is correct
22 Correct 24 ms 34860 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 34788 KB Output is correct
2 Correct 2631 ms 213332 KB Output is correct
3 Correct 2045 ms 208144 KB Output is correct
4 Correct 2875 ms 242348 KB Output is correct
5 Correct 2421 ms 209696 KB Output is correct
6 Correct 1852 ms 188900 KB Output is correct
7 Correct 1622 ms 179640 KB Output is correct
8 Correct 605 ms 131116 KB Output is correct
9 Correct 3191 ms 246024 KB Output is correct
10 Correct 2732 ms 242276 KB Output is correct
11 Correct 2962 ms 212680 KB Output is correct
12 Correct 2552 ms 208888 KB Output is correct
13 Correct 712 ms 132584 KB Output is correct
14 Correct 841 ms 137164 KB Output is correct
15 Correct 951 ms 143248 KB Output is correct
16 Correct 968 ms 148596 KB Output is correct
17 Correct 1110 ms 155852 KB Output is correct
18 Correct 22 ms 34760 KB Output is correct
19 Correct 21 ms 34772 KB Output is correct
20 Correct 26 ms 34780 KB Output is correct
21 Correct 21 ms 34788 KB Output is correct
22 Correct 24 ms 34860 KB Output is correct
23 Correct 30 ms 34772 KB Output is correct
24 Incorrect 3112 ms 213196 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 34824 KB Output is correct
2 Execution timed out 4050 ms 243048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 34772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 34772 KB Output isn't correct
2 Halted 0 ms 0 KB -