oj.uz

Submission #1046359

# Submission time Handle Problem Language Result Execution time Memory
1046359 2024-08-06T13:29:01 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 450 ms 69500 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 n_, s, n, m, k, m_, par[N], *eh[N], eo[N], dep[N],
    ans[N], tin[N], tout[N], timer, *ph[A], po[A], *qh[A], qo[A], freq[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_;
  ++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;

    ++freq[dep[i]];
    for (int cur = i; cur != 0; cur = par[cur])
      if (cur <= n_)
        ++freq[dep[i]-dep[cur]];

    for (int j = 0; j <= n_; ++j)
      if (k - s - dep[j] >= 0)
        ans[i] |= freq[k - s - dep[j]];

    --freq[dep[i]];
    for (int cur = i; cur != 0; cur = par[cur])
      if (cur <= n_)
        --freq[dep[i]-dep[cur]];

    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:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d%d%d", &n_, &m_, &k, &s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:45:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d", &p, &l);
      |     ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 4440 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 81 ms 31252 KB Output is correct
2 Correct 77 ms 29268 KB Output is correct
3 Correct 90 ms 31088 KB Output is correct
4 Correct 80 ms 29268 KB Output is correct
5 Correct 431 ms 67408 KB Output is correct
6 Correct 450 ms 69500 KB Output is correct
7 Correct 262 ms 51024 KB Output is correct
8 Correct 256 ms 52900 KB Output is correct
9 Correct 82 ms 29656 KB Output is correct
10 Correct 80 ms 29004 KB Output is correct
11 Correct 77 ms 5688 KB Output is correct
12 Correct 349 ms 39740 KB Output is correct

Subtask #3
0 / 34.0

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