oj.uz

Submission #1046352

# Submission time Handle Problem Language Result Execution time Memory
1046352 2024-08-06T13:22:52 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 614 ms 65540 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 cc(const void *i, const void *j) {
  return *(int*)i-*(int*)j;
}

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

void dfs(int u) {
  assert(dep[u] <= k);
  tin[u] = timer++;
  if (dep[u] > k) dep[u] = k + 1;
  for (int j = 0; j < eo[u]; j += 2) {
    int v = eh[u][j], l = eh[u][j+1];
    dep[v] = l + dep[u];
    dfs(v);
  }
  tout[u] = timer;
}

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

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

  dfs(0);

  for (int i = n_ + 1; i <= n; ++i) {

    if (dep[i] == k)
      ans[i] = 1;

    /* one symlink use */
    o = 1;
    chain[0] = dep[i];
    for (int cur = i; cur != 0; cur = par[cur])
      if (cur <= n_)
        chain[o++] = dep[i] - dep[cur];

    qsort(chain, o, sizeof *chain, cc);

    for (int j = 0; j <= n_; ++j) {
      int left = k - s - dep[j], md, lb = 0, ub = o;
      while (ub - lb > 1)
        if (chain[md = lb + (ub - lb) / 2] <= left) lb = md;
        else ub = md;
      ans[i] |= (chain[lb] == left);
    }

    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);
      }

      if (del == 1) {
        for (int ll = l; 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:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d%d%d%d", &n, &m, &k, &s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:52:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 4444 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 93 ms 27236 KB Output is correct
2 Correct 91 ms 27216 KB Output is correct
3 Correct 95 ms 25180 KB Output is correct
4 Correct 91 ms 27348 KB Output is correct
5 Correct 614 ms 65540 KB Output is correct
6 Correct 589 ms 63444 KB Output is correct
7 Correct 401 ms 49204 KB Output is correct
8 Correct 409 ms 47256 KB Output is correct
9 Correct 117 ms 27728 KB Output is correct
10 Correct 95 ms 23020 KB Output is correct
11 Correct 126 ms 5540 KB Output is correct
12 Correct 494 ms 37420 KB Output is correct

Subtask #3
0 / 34.0

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