oj.uz

Submission #1046320

# Submission time Handle Problem Language Result Execution time Memory
1046320 2024-08-06T12:56:19 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 469 ms 54864 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 6005
#define A 1000005

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

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

void factors(int x) {
  f[0] = 1;
  fo = 1;
  for (int j = 2; j * j <= x; ++j)
    if (x % j == 0) {
      f[fo++] = j;
      if (x != x / j)
        f[fo++] = x / j;
    }
}

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

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

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) {
    int cycle;

    if (dep[i] == k) {
      ans[i] = 1;
      goto Next;
    }

    /* one symlink traversal */
    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];
      if (left > 0) {
        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;
          goto Next;
        }
      }
    }

    cycle = k - dep[i];
    if (cycle > 0) {
      factors(cycle);
      for (int j = 0; j < fo; ++j)
        pus(ph, po, f[j], i);
    }
Next:;
  }

  for (int i = 0; i <= n_; ++i)
    for (int j = 0; j <= n_; ++j)
      if (dep[j] > dep[i] && 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 low, j = 0; j < qo[l]; ++j) {
      low = qh[l][j];
      add(tin[low], 1);
      add(tout[low] + 1, -1);
    }

    for (int j = 0; j < po[l]; ++j)
      if (sum(tin[ph[l][j]]))
        ans[ph[l][j]] = 1;

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

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

Compilation message

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

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 51 ms 17092 KB Output is correct
2 Correct 42 ms 16728 KB Output is correct
3 Correct 42 ms 17244 KB Output is correct
4 Correct 46 ms 17232 KB Output is correct
5 Correct 469 ms 53240 KB Output is correct
6 Correct 465 ms 54864 KB Output is correct
7 Correct 262 ms 37676 KB Output is correct
8 Correct 280 ms 38484 KB Output is correct
9 Correct 38 ms 16220 KB Output is correct
10 Correct 34 ms 15196 KB Output is correct
11 Correct 18 ms 5692 KB Output is correct
12 Correct 375 ms 37240 KB Output is correct

Subtask #3
0 / 34.0

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