Submission #544596

#	Time	Username	Problem	Language	Result	Execution time	Memory
544596		pavement	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	3387 ms	324500 KiB

sprinkler

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;


#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
void read(int &v) {
	v = 0;
	char ch = getchar_unlocked();
	for (; ch < '0' || ch > '9'; ch = getchar_unlocked());
	for (; '0' <= ch && ch <= '9'; ch = getchar_unlocked())
		v = (v << 3) + (v << 1) + (ch & 15);
}

int N, L, Q, cent, cur_cent, cur_sz, anc[18][200005], dep[200005], H[200005], chd[200005], idx[200005], par[200005], sz[200005], dist_pre[200005][18];
bool proc[200005];
vector<int> adj[200005], adj2[200005];
vector<vector<int> > ft[200005], ft2[200005];

void init(int n, int e = -1) {
	anc[0][n] = e;
	for (int i = 1; i <= 17; i++)
		if (anc[i - 1][n] != -1) anc[i][n] = anc[i - 1][anc[i - 1][n]];
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		init(u, n);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int i = 17; i >= 0; i--)
		if (dep[v] - (1 << i) >= dep[u]) v = anc[i][v];
	if (u == v) return u;
	for (int i = 17; i >= 0; i--)
		if (anc[i][u] != anc[i][v]) {
			u = anc[i][u];
			v = anc[i][v];
		}
	return anc[0][u];
}

int dist(int u, int v) {
	int tmp = dep[u] + dep[v] - 2 * dep[lca(u, v)];
	return tmp;
}

int get_sz(int n, int e = -1) {
	par[n] = cur_cent;
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e && !proc[u])
		sz[n] += get_sz(u, n);
	return sz[n];
}

void get_cent(int n, int e = -1) {
	int m = 0;
	for (auto u : adj[n]) if (u != e && !proc[u]) {
		m = max(m, sz[u]);
		get_cent(u, n);
	}
	m = max(m, cur_sz - sz[n]);
	if (m <= cur_sz / 2) cent = n;
}

void decomp(int n, int e = -1) {
	cur_cent = e;
	get_sz(n);
	cur_sz = sz[n];
	get_cent(n);
	int tmp_cent = cent;
	proc[cent] = 1;
	for (auto u : adj[tmp_cent])
		if (!proc[u]) decomp(u, tmp_cent);
}

int ls(int x) { return x & -x; }  

void pupd(int p, int a, int d, int v) {
	if (d < 0) return;
	for (int cpy_d = d; a <= chd[p]; a += ls(a))
		for (d = cpy_d + 1; d <= 41; d += ls(d))
			ft[p][a][d] = (ll)ft[p][a][d] * (ll)v % L;
}

void supd(int p, int a, int d, int v) {
	if (d < 0) return;
	int cpy_d = d + 1;
	for (a = chd[p] - a + 1; a <= chd[p]; a += ls(a))
		for (d = cpy_d; d <= 41; d += ls(d))
			ft2[p][a][d] = (ll)ft2[p][a][d] * (ll)v % L;
}

void upd(int p, int a, int d, int v) {
	if (d < 0) return;
	d = 40 - d;
	pupd(p, a, d, v);
	supd(p, a, d, v);
}

int pqry(int p, int a, int d) {
	if (d < 0) return 1;
	int r = 1;
	for (int cpy_d = d + 1; a; a -= ls(a))
		for (d = cpy_d; d; d -= ls(d))
			r = (ll)r * (ll)ft[p][a][d] % L;
	return r;
}

int sqry(int p, int a, int d) {
	if (d < 0) return 1;
	int r = 1, cpy_d = d + 1;
	for (a = chd[p] - a + 1; a; a -= ls(a))
		for (d = cpy_d; d; d -= ls(d)) r = (ll)r * (ll)ft2[p][a][d] % L;
	return r;
}

int qry(int p, int a, int d) {
	if (d > 40) return 1;
	d = 40 - d;
	if (a == -1) return pqry(p, chd[p], d);
	return (ll)pqry(p, a - 1, d) * (ll)sqry(p, a + 1, d) % L;
}

main() {
	memset(anc, -1, sizeof anc);
	read(N);
	read(L);
	for (int i = 1, u, v; i < N; i++) {
		read(u);
		read(v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	init(1);
	decomp(1);
	for (int i = 1; i <= N; i++)
		if (par[i] != -1) adj2[par[i]].pb(i);
	for (int i = 1; i <= N; i++) {
		chd[i] = adj2[i].size() + 1;
		for (int j = 0; j < adj2[i].size(); j++)
			idx[adj2[i][j]] = j + 2;
		ft[i].resize(chd[i] + 1);
		for (auto &j : ft[i]) j.resize(42, 1);
		ft2[i].resize(chd[i] + 1);
		for (auto &j : ft2[i]) j.resize(42, 1);
	}
	for (int i = 1; i <= N; i++)
		for (int k = 0, curr = i; curr != -1; curr = par[curr], k++)
			dist_pre[i][k] = dist(i, curr);
	for (int i = 1; i <= N; i++) read(H[i]);
	read(Q);
	for (int T, X, D, W; Q--; ) {
		read(T);
		if (T == 1) {
			read(X);
			read(D);
			read(W);
			for (int OX = X, prv = 1, k = 0; X != -1; prv = idx[X], X = par[X], k++)
				upd(X, prv, D - dist_pre[OX][k], W);
		} else {
			read(X);
			int ans = 1, OX = X;
			for (int prv = -1, k = 0; X != -1; prv = idx[X], X = par[X], k++)
				ans = (ll)ans * (ll)qry(X, prv, dist_pre[OX][k]) % L;
			printf("%lld\n", (ll)ans * (ll)H[OX] % L);
		}
	}
}

Compilation message (stderr)

sprinkler.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main() {
      | ^~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |   for (int j = 0; j < adj2[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17