oj.uz

답안 #1046346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046346 2024-08-06T13:18:14 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 616 ms 64452 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, f[N], fo,
    ans[N], tin[N], tout[N], timer, *ph[A], po[A], *qh[A], qo[A];

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

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: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

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

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 27020 KB Output is correct
2 Correct 92 ms 26936 KB Output is correct
3 Correct 102 ms 24924 KB Output is correct
4 Correct 106 ms 27036 KB Output is correct
5 Correct 605 ms 64452 KB Output is correct
6 Correct 616 ms 62208 KB Output is correct
7 Correct 383 ms 48224 KB Output is correct
8 Correct 400 ms 46420 KB Output is correct
9 Correct 110 ms 27220 KB Output is correct
10 Correct 101 ms 22616 KB Output is correct
11 Correct 145 ms 5972 KB Output is correct
12 Correct 466 ms 37204 KB Output is correct

Subtask #3
0 / 34.0

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