oj.uz

답안 #1046338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046338 2024-08-06T13:08:29 Z sleepntsheep File Paths (BOI15_fil) C
33 / 100
 543 ms 64660 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) {
    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];
      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 (!ans[i] && 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 (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);
    }

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

  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 5 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 27348 KB Output is correct
2 Correct 64 ms 27220 KB Output is correct
3 Correct 36 ms 25180 KB Output is correct
4 Correct 66 ms 27152 KB Output is correct
5 Correct 535 ms 64660 KB Output is correct
6 Correct 543 ms 62548 KB Output is correct
7 Correct 329 ms 48988 KB Output is correct
8 Correct 332 ms 47028 KB Output is correct
9 Correct 50 ms 27728 KB Output is correct
10 Correct 40 ms 22864 KB Output is correct
11 Correct 70 ms 5556 KB Output is correct
12 Correct 415 ms 37232 KB Output is correct

Subtask #3
0 / 34.0

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