oj.uz

답안 #1046324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046324 2024-08-06T12:58:03 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 469 ms 54868 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, 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 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;
          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:;
  }

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

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 17464 KB Output is correct
2 Correct 42 ms 17496 KB Output is correct
3 Correct 41 ms 17496 KB Output is correct
4 Correct 48 ms 17500 KB Output is correct
5 Correct 469 ms 53456 KB Output is correct
6 Correct 430 ms 54868 KB Output is correct
7 Correct 273 ms 37848 KB Output is correct
8 Correct 298 ms 38404 KB Output is correct
9 Correct 38 ms 17500 KB Output is correct
10 Correct 34 ms 15196 KB Output is correct
11 Correct 21 ms 5724 KB Output is correct
12 Correct 393 ms 37200 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -