oj.uz

Submission #1046351

# Submission time Handle Problem Language Result Execution time Memory
1046351 2024-08-06T13:21:30 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 613 ms 64336 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;
  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];
      int md, lb = 0, ub = o;
      while (ub - lb > 1)
        if (chain[md = lb + (ub - lb) / 2] <= left) lb = md;
        else ub = md;
      if (chain[lb] == left)
        ans[i] = 1;
    }

    if (!ans[i] && 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: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:51:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 4636 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 91 ms 26940 KB Output is correct
2 Correct 89 ms 26972 KB Output is correct
3 Correct 102 ms 24948 KB Output is correct
4 Correct 91 ms 26960 KB Output is correct
5 Correct 613 ms 64336 KB Output is correct
6 Correct 590 ms 62032 KB Output is correct
7 Correct 393 ms 48252 KB Output is correct
8 Correct 390 ms 46160 KB Output is correct
9 Correct 105 ms 27220 KB Output is correct
10 Correct 93 ms 22492 KB Output is correct
11 Correct 124 ms 5712 KB Output is correct
12 Correct 468 ms 37176 KB Output is correct

Subtask #3
0 / 34.0

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