oj.uz

Submission #1046355

# Submission time Handle Problem Language Result Execution time Memory
1046355 2024-08-06T13:25:12 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 593 ms 65364 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) {
  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_ = 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] + 1, 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:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d%d%d", &n, &m, &k, &s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:49:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 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 92 ms 27220 KB Output is correct
2 Correct 94 ms 27296 KB Output is correct
3 Correct 91 ms 25168 KB Output is correct
4 Correct 91 ms 27216 KB Output is correct
5 Correct 588 ms 65364 KB Output is correct
6 Correct 593 ms 63508 KB Output is correct
7 Correct 410 ms 49192 KB Output is correct
8 Correct 385 ms 46928 KB Output is correct
9 Correct 108 ms 27808 KB Output is correct
10 Correct 94 ms 23020 KB Output is correct
11 Correct 132 ms 5840 KB Output is correct
12 Correct 462 ms 37192 KB Output is correct

Subtask #3
0 / 34.0

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