oj.uz

Submission #1046378

# Submission time Handle Problem Language Result Execution time Memory
1046378 2024-08-06T13:42:49 Z sleepntsheep File Paths (BOI15_fil) C
100 / 100
 511 ms 70996 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 6005
#define A 4000005

void pus(int **eh, int *eo, int i, int j) {
  int o = eo[i]++;
  if (!o) eh[i] = (int*)malloc(sizeof **eh * 2);
  else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
  eh[i][o] = j;
}

int ft[N];
void add(int p, int k) {
  for (; p < N; p |= p + 1) ft[p] += k;
}
int sum(int p) {
  int z = 0;
  for (++p; p > 0; p &= p - 1) z += ft[p - 1];
  return z;
}

int n_, s, n, m, k, m_, par[N], *eh[N], eo[N], dep[N],
    ans[N], tin[N], tout[N], timer = 1, *ph[A], po[A], *qh[A], qo[A], freq[A];

void dfs(int u) {
  tin[u] = timer++;
  for (int j = 0; j < eo[u]; ++j) dfs(eh[u][j]);
  tout[u] = timer;
}

int main(void) {
  scanf("%d%d%d%d", &n_, &m_, &k, &s);
  n = n_ + m_;
  ++s;

  for (int p, l, i = 1; i <= n; ++i) {
    scanf("%d%d", &p, &l);
    pus(eh, eo, par[i] = p, i);
    dep[i] = dep[p] + l + 1;
  }

  dfs(0);

  for (int i = n_ + 1; i <= n; ++i) {
    ans[i] |= dep[i] == k;

    for (int del = 1; del >= 0; --del) {
      freq[dep[i]] = del;
      for (int cur = i; cur != 0; cur = par[cur])
        if (cur <= n_)
          freq[dep[i]-dep[cur]] = del;

      for (int j = 0; del == 1 && j <= n_; ++j)
        if (k - s - dep[j] >= 0)
          ans[i] |= freq[k - s - dep[j]];
    }

    if (k > dep[i])
      pus(ph, po, k - dep[i], i);
  }

  /* many symlink uses */
  for (int i = 0; i <= n_; ++i)
    for (int j = 0; j <= n_; ++j)
      if (tin[i] <= tin[j] && tout[j] <= tout[i] && s + dep[j] - dep[i] < A) {
        pus(qh, qo, s + dep[j] - dep[i], i);
      }

  for (int l = 1; l < A; ++l) {
    for (int del = 1; del >= -1; del -= 2) {
      for (int low, j = 0; j < qo[l]; ++j) {
        low = qh[l][j];
        add(tin[low], del);
        add(tout[low], -del);
      }

      for (int ll = l; del == 1 && ll < A; ll += l)
        for (int j = 0; j < po[ll]; ++j)
          if (sum(tin[ph[ll][j]]) > 0)
            ans[ph[ll][j]] = 1;
    }
  }

  for (int i = n_ + 1; i <= n; ++i)
    puts(ans[i] ? "YES": "NO");
}

Compilation message

fil.c: In function 'pus':
fil.c:11:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |   else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                      ~~^~~
fil.c: In function 'main':
fil.c:35:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d%d%d", &n_, &m_, &k, &s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:40:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4440 KB Output is correct
2 Correct 60 ms 4788 KB Output is correct
3 Correct 59 ms 7796 KB Output is correct
4 Correct 72 ms 9048 KB Output is correct
5 Correct 73 ms 30936 KB Output is correct
6 Correct 66 ms 29272 KB Output is correct
7 Correct 75 ms 33372 KB Output is correct
8 Correct 62 ms 26732 KB Output is correct
9 Correct 67 ms 27736 KB Output is correct
10 Correct 59 ms 4616 KB Output is correct
11 Correct 59 ms 6748 KB Output is correct
12 Correct 68 ms 8280 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 31192 KB Output is correct
2 Correct 84 ms 30552 KB Output is correct
3 Correct 84 ms 32408 KB Output is correct
4 Correct 90 ms 30544 KB Output is correct
5 Correct 511 ms 67376 KB Output is correct
6 Correct 506 ms 70996 KB Output is correct
7 Correct 320 ms 52216 KB Output is correct
8 Correct 302 ms 52932 KB Output is correct
9 Correct 93 ms 29636 KB Output is correct
10 Correct 97 ms 30560 KB Output is correct
11 Correct 90 ms 7800 KB Output is correct
12 Correct 397 ms 41300 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4440 KB Output is correct
2 Correct 60 ms 4788 KB Output is correct
3 Correct 59 ms 7796 KB Output is correct
4 Correct 72 ms 9048 KB Output is correct
5 Correct 73 ms 30936 KB Output is correct
6 Correct 66 ms 29272 KB Output is correct
7 Correct 75 ms 33372 KB Output is correct
8 Correct 62 ms 26732 KB Output is correct
9 Correct 67 ms 27736 KB Output is correct
10 Correct 59 ms 4616 KB Output is correct
11 Correct 59 ms 6748 KB Output is correct
12 Correct 68 ms 8280 KB Output is correct
13 Correct 82 ms 31192 KB Output is correct
14 Correct 84 ms 30552 KB Output is correct
15 Correct 84 ms 32408 KB Output is correct
16 Correct 90 ms 30544 KB Output is correct
17 Correct 511 ms 67376 KB Output is correct
18 Correct 506 ms 70996 KB Output is correct
19 Correct 320 ms 52216 KB Output is correct
20 Correct 302 ms 52932 KB Output is correct
21 Correct 93 ms 29636 KB Output is correct
22 Correct 97 ms 30560 KB Output is correct
23 Correct 90 ms 7800 KB Output is correct
24 Correct 397 ms 41300 KB Output is correct
25 Correct 98 ms 29344 KB Output is correct
26 Correct 105 ms 30588 KB Output is correct
27 Correct 89 ms 31240 KB Output is correct
28 Correct 91 ms 32716 KB Output is correct
29 Correct 456 ms 69680 KB Output is correct
30 Correct 456 ms 68880 KB Output is correct
31 Correct 263 ms 53332 KB Output is correct
32 Correct 259 ms 52776 KB Output is correct
33 Correct 91 ms 30680 KB Output is correct
34 Correct 84 ms 32088 KB Output is correct
35 Correct 77 ms 7768 KB Output is correct
36 Correct 369 ms 43104 KB Output is correct