oj.uz

Submission #643607

# Submission time Handle Problem Language Result Execution time Memory
643607 2022-09-22T15:40:52 Z rainboy Sprinkler (JOI22_sprinkler) C
3 / 100
 4000 ms 644124 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define D	40

int *ej[N], eo[N], *ft1[N][D], *ft2[N][D], n, md;

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void update(int **ft, int i, int j_, int n, int m, int x) {
	int j;

	while (i < n) {
		j = j_;
		while (j < m) {
			ft[i][j] = (long long) ft[i][j] * x % md;
			j |= j + 1;
		}
		i |= i + 1;
	}
}

int query(int **ft, int i, int j_) {
	int j, x;

	x = 1;
	while (i >= 0) {
		j = j_;
		while (j >= 0) {
			x = (long long) x * ft[i][j] % md;
			j &= j + 1, j--;
		}
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int aa[N], pp[N], ta[N], ll[N], rr[N], qu[N];
	int q, h, i, j, c, d, o, head, cnt;

	scanf("%d%d", &n, &md);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	head = cnt = 0;
	pp[0] = -1, qu[head + cnt++] = 0;
	while (cnt) {
		i = qu[cnt--, head], ta[i] = head++;
		ll[i] = head + cnt;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (j != pp[i])
				pp[j] = i, qu[head + cnt++] = j;
		}
		rr[i] = head + cnt;
	}
	for (i = 0; i < n; i++)
		eo[i] = rr[i] - ll[i];
	for (i = 0; i < n; i++)
		for (d = 0; d < D; d++) {
			ft1[i][d] = (int *) malloc(eo[i] * sizeof *ft1[i][d]);
			ft2[i][d] = (int *) malloc(eo[i] * sizeof *ft2[i][d]);
			for (h = 0; h < eo[i]; h++)
				ft1[i][d][h] = ft2[i][d][h] = 1;
		}
	scanf("%d", &q);
	while (q--) {
		int t, x, ans;

		scanf("%d%d", &t, &i), i--;
		if (t == 1) {
			scanf("%d%d", &d, &x);
			for (c = 0, j = -1; c <= d && i != -1; c++, j = i, i = pp[i]) {
				aa[i] = (long long) aa[i] * x % md;
				if (c < d) {
					if (c == 0)
						update(ft1[i], D - d + c, 0, D, eo[i], x);
					else {
						update(ft1[i], D - d + c, ta[j] - ll[i] + 1, D, eo[i], x);
						update(ft2[i], D - d + c, rr[i] - ta[j], D, eo[i], x);
					}
				}
			}
		} else {
			ans = aa[i];
			for (c = 1, j = i, i = pp[i]; c <= D && i != -1; c++, j = i, i = pp[i]) {
				ans = (long long) ans * query(ft1[i], D - c, ta[j] - ll[i]) % md;
				ans = (long long) ans * query(ft2[i], D - c, rr[i] - 1 - ta[j]) % md;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

sprinkler.c: In function 'append':
sprinkler.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
sprinkler.c: In function 'main':
sprinkler.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d", &n, &md);
      |  ^~~~~~~~~~~~~~~~~~~~~~
sprinkler.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
sprinkler.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
sprinkler.c:79:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
sprinkler.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d", &t, &i), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~
sprinkler.c:85:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    scanf("%d%d", &d, &x);
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 5 ms 3540 KB Output is correct
5 Correct 5 ms 3540 KB Output is correct
6 Correct 4 ms 3540 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 4 ms 3824 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 392 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 396 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4078 ms 644124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4078 ms 644124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4072 ms 640744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 4089 ms 643388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 5 ms 3540 KB Output is correct
5 Correct 5 ms 3540 KB Output is correct
6 Correct 4 ms 3540 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 4 ms 3824 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 392 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 396 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Execution timed out 4078 ms 644124 KB Time limit exceeded
31 Halted 0 ms 0 KB -