Submission #643606

#TimeUsernameProblemLanguageResultExecution timeMemory
643606rainboySprinkler (JOI22_sprinkler)C11
0 / 100
4108 ms715604 KiB
#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 (stderr)

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);
      |    ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...