Submission #551749

#	Time	Username	Problem	Language	Result	Execution time	Memory
551749		nonsensenonsense1	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4089 ms	84104 KiB

sprinkler

#pragma GCC optimize("O3,unroll-loops")
#include <cstdio>
#include <vector>

int md;
inline int mul(int a, int b) {
	return (long long)a * b % md;
}

const int N = 200000;
const int LG = 19;
const int K = 500;
std::vector<int> g[N], list[N], t[N];
int q, n, dep[N], pr[N], pos[N], h[N], start[N], out[N], amt, st[LG][N * 2];

void dfs(int v) {
	static int dt = 0;
	++dt;
	pos[v] = list[dep[v]].size();
	list[dep[v]].push_back(v);
	start[v] = amt;
	st[0][amt++] = dep[v];
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr[v]) {
		st[0][amt++] = dep[v];
		pr[g[v][i]] = v;
		dep[g[v][i]] = dep[v] + 1;
		dfs(g[v][i]);
	}
	out[v] = dt;
}

int l;
int dlca(int u, int v) {
	u = start[u];
	v = start[v];
	if (u > v) std::swap(u, v);
	++v;
	l = 31 - __builtin_clz(v - u);
	return std::min(st[l][u], st[l][v - (1 << l)]);
}

int f(int u, int v) {
	return dep[u] + dep[v] - 2 * dlca(u, v);
}

void update(std::vector<int> &t, int l, int r, int x) {
	if (!x) {
		for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) t[l++] = 0;
			if (r & 1) t[--r] = 0;
		}
		return;
	}
	for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			t[l] = mul(t[l], x);
			++l;
		}
		if (r & 1) {
			--r;
			t[r] = mul(t[r], x);
		}
	}
}

int get(std::vector<int> &t, int i) {
	int res = 1;
	for (i += t.size() >> 1; i > 0; i >>= 1) res = mul(res, t[i]);
	return res;
}

int main() {
	scanf("%d%d", &n, &md);
	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	dfs(0);
	for (int j = 1; j < LG; ++j) for (int i = 0; i + (1 << j) <= 2 * n; ++i) st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
	for (int i = 0; i < n; ++i) scanf("%d", h + i);
	for (int i = 0; i < n; ++i) t[i].resize(list[i].size() << 1, 1);
	scanf("%d", &q);
	while (q--) {
		int type, v;
		scanf("%d%d", &type, &v);
		--v;
		if (type == 1) {
			int dist, x;
			scanf("%d%d", &dist, &x);
			for (int i = dep[v] + dist; i >= std::max(0, dep[v] - dist); --i) {
				int l = 0, r = list[i].size();
				while (l < r) {
					int m = l + r >> 1;
					if (out[list[i][m]] >= out[v] || f(v, list[i][m]) <= dist) r = m;
					else l = m + 1;
				}
				int fi = r;
				l = r, r = list[i].size();
				while (l < r) {
					int m = l + r >> 1;
					if (out[list[i][m]] >= out[v] && f(v, list[i][m]) > dist) r = m;
					else l = m + 1;
				}
				update(t[i], fi, r, x);
			}
		} else printf("%d\n", mul(h[v], get(t[dep[v]], pos[v])));
	}
	return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:81:131: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   81 |  for (int j = 1; j < LG; ++j) for (int i = 0; i + (1 << j) <= 2 * n; ++i) st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
      |                                                                                                                                 ~~^~~
sprinkler.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |      int m = l + r >> 1;
      |              ~~^~~
sprinkler.cpp:102:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |      int m = l + r >> 1;
      |              ~~^~~
sprinkler.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d", &n, &md);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:82:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  for (int i = 0; i < n; ++i) scanf("%d", h + i);
      |                              ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d", &type, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    scanf("%d%d", &dist, &x);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

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