oj.uz

Submission #551761

# Submission time Handle Problem Language Result Execution time Memory
551761 2022-04-21T13:00:16 Z nonsensenonsense1 Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 150120 KB 
#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 = 200005;
const int D = 40;
const int LG = 19;
const int K = 500;
std::vector<int> g[N], list[N], t[N];
int q, n, in[N], dep[N], pr[N], pos[N], h[N], start[N], out[N], amt, st[LG][N * 2], clz[N * 2], bounds[N][D + 1][2];

void dfs(int v) {
	static int dt = 0;
	in[v] = 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]) {
		if (i) 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 = 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 sub_left(int v, int dep) {
	int l = 0, r = (int)list[dep].size();
	while (l < r) {
		int m = l + r >> 1;
		if (in[list[dep][m]] >= in[v]) r = m;
		else l = m + 1;
	}
	return r;
}

int sub_right(int v, int dep) {
	int l = 0, r = (int)list[dep].size();
	while (l < r) {
		int m = l + r >> 1;
		if (out[list[dep][m]] > out[v]) r = m;
		else l = m + 1;
	}
	return r;
}

int main() {
	scanf("%d%d", &n, &md);
	clz[1] = 0;
	for (int i = 2; i <= 2 * n; ++i) {
		clz[i] = clz[i - 1];
		while (1 << clz[i] + 1 <= i) ++clz[i];
	}
	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);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= D && dep[i] + j < n; ++j) {
			bounds[i][j][0] = sub_left(i, dep[i] + j);
			bounds[i][j][1] = sub_right(i, dep[i] + j);
		}
	}
	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 = std::min(n - 1, dep[v] + dist), j = v; i >= std::max(0, dep[v] - dist); --i) {
				while (j && dep[v] + i - 2 * (dep[j] - 1) <= dist) j = pr[j];
				int l = bounds[j][i - dep[j]][0], r = bounds[j][i - dep[j]][1];
				update(t[i], l, r, x);
			}
		} else printf("%d\n", mul(h[v], get(t[dep[v]], pos[v])));
	}
	return 0;
}

Compilation message

sprinkler.cpp: In function 'int sub_left(int, int)':
sprinkler.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int m = l + r >> 1;
      |           ~~^~~
sprinkler.cpp: In function 'int sub_right(int, int)':
sprinkler.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int m = l + r >> 1;
      |           ~~^~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:98:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   98 |   while (1 << clz[i] + 1 <= i) ++clz[i];
      |               ~~~~~~~^~~
sprinkler.cpp:107:131: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |  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:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d%d", &n, &md);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:108:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  for (int i = 0; i < n; ++i) scanf("%d", h + i);
      |                              ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d%d", &type, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:123:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |    scanf("%d%d", &dist, &x);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 12 ms 14420 KB Output is correct
4 Correct 12 ms 14960 KB Output is correct
5 Correct 12 ms 15000 KB Output is correct
6 Correct 11 ms 14932 KB Output is correct
7 Correct 12 ms 14996 KB Output is correct
8 Correct 14 ms 14976 KB Output is correct
9 Correct 12 ms 14420 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 10 ms 14420 KB Output is correct
13 Correct 11 ms 14420 KB Output is correct
14 Correct 10 ms 14432 KB Output is correct
15 Correct 13 ms 14420 KB Output is correct
16 Correct 14 ms 14344 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 12 ms 14420 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Correct 12 ms 14420 KB Output is correct
21 Correct 10 ms 14420 KB Output is correct
22 Correct 9 ms 14472 KB Output is correct
23 Correct 13 ms 14464 KB Output is correct
24 Correct 13 ms 14340 KB Output is correct
25 Correct 13 ms 14452 KB Output is correct
26 Correct 10 ms 14464 KB Output is correct
27 Correct 12 ms 14476 KB Output is correct
28 Correct 12 ms 14476 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 1998 ms 125732 KB Output is correct
3 Correct 2124 ms 122568 KB Output is correct
4 Correct 654 ms 139272 KB Output is correct
5 Correct 2033 ms 124372 KB Output is correct
6 Correct 1508 ms 123956 KB Output is correct
7 Correct 1258 ms 124104 KB Output is correct
8 Correct 661 ms 124824 KB Output is correct
9 Correct 693 ms 150120 KB Output is correct
10 Correct 966 ms 144644 KB Output is correct
11 Correct 1998 ms 125700 KB Output is correct
12 Correct 2217 ms 122544 KB Output is correct
13 Correct 921 ms 123784 KB Output is correct
14 Correct 804 ms 123084 KB Output is correct
15 Correct 901 ms 123300 KB Output is correct
16 Correct 805 ms 123144 KB Output is correct
17 Correct 901 ms 123572 KB Output is correct
18 Correct 10 ms 14420 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Correct 10 ms 14452 KB Output is correct
21 Correct 10 ms 14472 KB Output is correct
22 Correct 10 ms 14388 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 1998 ms 125732 KB Output is correct
3 Correct 2124 ms 122568 KB Output is correct
4 Correct 654 ms 139272 KB Output is correct
5 Correct 2033 ms 124372 KB Output is correct
6 Correct 1508 ms 123956 KB Output is correct
7 Correct 1258 ms 124104 KB Output is correct
8 Correct 661 ms 124824 KB Output is correct
9 Correct 693 ms 150120 KB Output is correct
10 Correct 966 ms 144644 KB Output is correct
11 Correct 1998 ms 125700 KB Output is correct
12 Correct 2217 ms 122544 KB Output is correct
13 Correct 921 ms 123784 KB Output is correct
14 Correct 804 ms 123084 KB Output is correct
15 Correct 901 ms 123300 KB Output is correct
16 Correct 805 ms 123144 KB Output is correct
17 Correct 901 ms 123572 KB Output is correct
18 Correct 10 ms 14420 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Correct 10 ms 14452 KB Output is correct
21 Correct 10 ms 14472 KB Output is correct
22 Correct 10 ms 14388 KB Output is correct
23 Correct 9 ms 14468 KB Output is correct
24 Correct 1981 ms 125720 KB Output is correct
25 Correct 2381 ms 122548 KB Output is correct
26 Correct 765 ms 147340 KB Output is correct
27 Correct 2045 ms 124152 KB Output is correct
28 Correct 1409 ms 124060 KB Output is correct
29 Correct 1248 ms 124148 KB Output is correct
30 Correct 806 ms 124764 KB Output is correct
31 Correct 912 ms 141784 KB Output is correct
32 Correct 978 ms 144744 KB Output is correct
33 Correct 1912 ms 125740 KB Output is correct
34 Correct 2227 ms 122524 KB Output is correct
35 Correct 12 ms 14412 KB Output is correct
36 Correct 10 ms 14420 KB Output is correct
37 Correct 10 ms 14420 KB Output is correct
38 Correct 10 ms 14420 KB Output is correct
39 Correct 10 ms 14420 KB Output is correct
40 Correct 11 ms 14420 KB Output is correct
41 Correct 10 ms 14420 KB Output is correct
42 Correct 9 ms 14472 KB Output is correct
43 Correct 12 ms 14376 KB Output is correct
44 Correct 11 ms 14476 KB Output is correct
45 Correct 10 ms 14336 KB Output is correct
46 Correct 10 ms 14460 KB Output is correct
47 Correct 10 ms 14440 KB Output is correct
48 Correct 13 ms 14420 KB Output is correct
49 Correct 13 ms 14420 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 1384 ms 147044 KB Output is correct
3 Correct 3950 ms 139636 KB Output is correct
4 Correct 1721 ms 141428 KB Output is correct
5 Correct 3379 ms 122528 KB Output is correct
6 Correct 1670 ms 122384 KB Output is correct
7 Correct 1415 ms 122620 KB Output is correct
8 Correct 738 ms 123320 KB Output is correct
9 Correct 1406 ms 139184 KB Output is correct
10 Correct 3545 ms 143916 KB Output is correct
11 Correct 2830 ms 122908 KB Output is correct
12 Execution timed out 4070 ms 122232 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14420 KB Output is correct
2 Correct 1300 ms 140732 KB Output is correct
3 Execution timed out 4078 ms 133852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 12 ms 14420 KB Output is correct
4 Correct 12 ms 14960 KB Output is correct
5 Correct 12 ms 15000 KB Output is correct
6 Correct 11 ms 14932 KB Output is correct
7 Correct 12 ms 14996 KB Output is correct
8 Correct 14 ms 14976 KB Output is correct
9 Correct 12 ms 14420 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 10 ms 14420 KB Output is correct
13 Correct 11 ms 14420 KB Output is correct
14 Correct 10 ms 14432 KB Output is correct
15 Correct 13 ms 14420 KB Output is correct
16 Correct 14 ms 14344 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 12 ms 14420 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Correct 12 ms 14420 KB Output is correct
21 Correct 10 ms 14420 KB Output is correct
22 Correct 9 ms 14472 KB Output is correct
23 Correct 13 ms 14464 KB Output is correct
24 Correct 13 ms 14340 KB Output is correct
25 Correct 13 ms 14452 KB Output is correct
26 Correct 10 ms 14464 KB Output is correct
27 Correct 12 ms 14476 KB Output is correct
28 Correct 12 ms 14476 KB Output is correct
29 Correct 11 ms 14420 KB Output is correct
30 Correct 1998 ms 125732 KB Output is correct
31 Correct 2124 ms 122568 KB Output is correct
32 Correct 654 ms 139272 KB Output is correct
33 Correct 2033 ms 124372 KB Output is correct
34 Correct 1508 ms 123956 KB Output is correct
35 Correct 1258 ms 124104 KB Output is correct
36 Correct 661 ms 124824 KB Output is correct
37 Correct 693 ms 150120 KB Output is correct
38 Correct 966 ms 144644 KB Output is correct
39 Correct 1998 ms 125700 KB Output is correct
40 Correct 2217 ms 122544 KB Output is correct
41 Correct 921 ms 123784 KB Output is correct
42 Correct 804 ms 123084 KB Output is correct
43 Correct 901 ms 123300 KB Output is correct
44 Correct 805 ms 123144 KB Output is correct
45 Correct 901 ms 123572 KB Output is correct
46 Correct 10 ms 14420 KB Output is correct
47 Correct 10 ms 14420 KB Output is correct
48 Correct 10 ms 14452 KB Output is correct
49 Correct 10 ms 14472 KB Output is correct
50 Correct 10 ms 14388 KB Output is correct
51 Correct 9 ms 14468 KB Output is correct
52 Correct 1981 ms 125720 KB Output is correct
53 Correct 2381 ms 122548 KB Output is correct
54 Correct 765 ms 147340 KB Output is correct
55 Correct 2045 ms 124152 KB Output is correct
56 Correct 1409 ms 124060 KB Output is correct
57 Correct 1248 ms 124148 KB Output is correct
58 Correct 806 ms 124764 KB Output is correct
59 Correct 912 ms 141784 KB Output is correct
60 Correct 978 ms 144744 KB Output is correct
61 Correct 1912 ms 125740 KB Output is correct
62 Correct 2227 ms 122524 KB Output is correct
63 Correct 12 ms 14412 KB Output is correct
64 Correct 10 ms 14420 KB Output is correct
65 Correct 10 ms 14420 KB Output is correct
66 Correct 10 ms 14420 KB Output is correct
67 Correct 10 ms 14420 KB Output is correct
68 Correct 11 ms 14420 KB Output is correct
69 Correct 10 ms 14420 KB Output is correct
70 Correct 9 ms 14472 KB Output is correct
71 Correct 12 ms 14376 KB Output is correct
72 Correct 11 ms 14476 KB Output is correct
73 Correct 10 ms 14336 KB Output is correct
74 Correct 10 ms 14460 KB Output is correct
75 Correct 10 ms 14440 KB Output is correct
76 Correct 13 ms 14420 KB Output is correct
77 Correct 13 ms 14420 KB Output is correct
78 Correct 10 ms 14420 KB Output is correct
79 Correct 1384 ms 147044 KB Output is correct
80 Correct 3950 ms 139636 KB Output is correct
81 Correct 1721 ms 141428 KB Output is correct
82 Correct 3379 ms 122528 KB Output is correct
83 Correct 1670 ms 122384 KB Output is correct
84 Correct 1415 ms 122620 KB Output is correct
85 Correct 738 ms 123320 KB Output is correct
86 Correct 1406 ms 139184 KB Output is correct
87 Correct 3545 ms 143916 KB Output is correct
88 Correct 2830 ms 122908 KB Output is correct
89 Execution timed out 4070 ms 122232 KB Time limit exceeded
90 Halted 0 ms 0 KB -