oj.uz

Submission #1046368

# Submission time Handle Problem Language Result Execution time Memory
1046368 2024-08-06T13:34:48 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 459 ms 70668 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 >= -1; del -= 2) {
      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], j);

  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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 31208 KB Output is correct
2 Correct 81 ms 30564 KB Output is correct
3 Correct 80 ms 32592 KB Output is correct
4 Correct 81 ms 30552 KB Output is correct
5 Correct 427 ms 67376 KB Output is correct
6 Correct 459 ms 70668 KB Output is correct
7 Correct 244 ms 52200 KB Output is correct
8 Correct 247 ms 53208 KB Output is correct
9 Correct 85 ms 29532 KB Output is correct
10 Correct 80 ms 30108 KB Output is correct
11 Correct 100 ms 7772 KB Output is correct
12 Correct 322 ms 41296 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4640 KB Output isn't correct
2 Halted 0 ms 0 KB -