oj.uz

Submission #1046329

# Submission time Handle Problem Language Result Execution time Memory
1046329 2024-08-06T13:01:18 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 623 ms 59724 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) {
  fo = 0;
  for (int j = 1; j * j <= x; ++j)
    if (x % j == 0)
      f[fo++] = 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];
    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;

    /* 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];
      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;
      }
    }

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

  /* many symlink uses */
  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:35:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                      ~~^~~
fil.c: In function 'main':
fil.c:51:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d%d%d", &n, &m, &k, &s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:58:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 52 ms 20820 KB Output is correct
2 Correct 50 ms 20960 KB Output is correct
3 Correct 58 ms 21116 KB Output is correct
4 Correct 58 ms 21072 KB Output is correct
5 Correct 589 ms 58200 KB Output is correct
6 Correct 623 ms 59724 KB Output is correct
7 Correct 385 ms 42776 KB Output is correct
8 Correct 357 ms 43624 KB Output is correct
9 Correct 54 ms 20960 KB Output is correct
10 Correct 42 ms 18508 KB Output is correct
11 Correct 77 ms 5716 KB Output is correct
12 Correct 455 ms 37588 KB Output is correct

Subtask #3
0 / 34.0

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