oj.uz

답안 #1043605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043605 2024-08-04T11:54:42 Z sleepntsheep LOSTIKS (INOI20_lostiks) C
0 / 100
 29 ms 34524 KB 
#include <stdio.h>
#include <stdlib.h>

#define N 1000001
#define N_ (1<<20)

int n, s, t, *eh[N], eo[N], dep[N], up[N], par[N], sz[N], hld[N], tin[N], temp,
    st[N_ * 2], uu[N], vv[N], timer, aux[N];

void add(int p, int k) {
  st[p += N_] += k;
  for (; p /= 2; ) 
    st[p] = st[p * 2] + st[p * 2 + 1];
}

int query(int l, int r) {
  int z = 0;
  l += N_;
  r += N_ + 1;
  for (; l < r; l /= 2, r /= 2) {
    if (l & 1) z = z + st[l++];
    if (r & 1) z = st[--r] + z;
  }
  return z;
}

int search_rightmost(int v, int l, int r, int k) {
  if (l == r) return (k - st[v]) ? l - 1 : l;
  if (st[v * 2 + 1] >= k) return search_rightmost(2 * v + 1, (l+r)/2 + 1, r, k);
  else return search_rightmost(2 * v, l, (l+r)/2, k - st[v * 2 + 1]);
}

int search_leftmost(int v, int l, int r, int k) {
  if (l == r) return (k - st[v]) ? l + 1 : l;
  if (st[v * 2] >= k) return search_leftmost(2 * v, l, (l+r)/2, k);
  else return search_leftmost(2 * v + 1, (l+r)/2+1, r, k - st[v * 2]);
}

int upper(int key_pos) {
  return up[uu[key_pos]] == key_pos ? uu[key_pos] : vv[key_pos];
}

void pus(int i, int j) {
  int o = eo[i]++;
  if (!o) eh[i] = (int*)malloc(2 * sizeof**eh);
  else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
  eh[i][o] = j;
}

void dfs(int u, int p) {
  sz[u] = 1;
  dep[u] = dep[par[u] = p] + 1;
  for (int j = 0; j < eo[u]; j += 2) if (eh[u][j] != p) {
    up[eh[u][j]] = eh[u][j+1];
    dfs(eh[u][j], u);
    sz[u] += sz[eh[u][j]];
    if (eh[u][0] == p || sz[eh[u][0]] < sz[eh[u][j]])
      temp = eh[u][0], eh[u][0] = eh[u][j], eh[u][j] = temp;
  }
}

void efs(int u, int h) {
  aux[tin[u] = ++timer] = u;
  hld[u] = h;
  for (int j = 0; j < eo[u]; j += 2) if (eh[u][j] != par[u])
    efs(eh[u][j], j ? eh[u][j] : h);
}

int lca(int u, int v) {
  while (hld[u] != hld[v]) {
    if (dep[hld[u]] > dep[hld[v]]) u = par[hld[u]];
    else v = par[hld[v]];
  }
  return dep[u] < dep[v] ? u : v;
}

int dist(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int query_path(int u, int v, int *a) {
  int z = 0;
  while (hld[u] != hld[v]) {
    if (dep[hld[u]] < dep[hld[v]]) temp = u, u = v, v = temp;
    z += query(tin[hld[u]], tin[u]);
    u = par[hld[u]];
  }
  if (u != v) {
    if (dep[u] < dep[v]) temp = u, u = v, v = temp;
    z += query(tin[v] + 1, tin[u]);
  }
  if (NULL != a) *a = v;
  return z;
}

int find_key(int s, int t) { /* first node that contain first key from s to t */
  int k, cc, a = lca(s, t);
  if (s != a) {
    for (; hld[a] != hld[s]; s = par[hld[s]]) {
      cc = query(tin[s] + 1, n);
      k = search_rightmost(1, 0, N_ - 1, cc + 1);
      if (tin[s] >= k && k >= tin[hld[s]])
        return up[aux[k]];
    }
    if (s != a) {
      cc = query(tin[s] + 1, n);
      k = search_rightmost(1, 0, N_ - 1, cc + 1);
      if (tin[s] >= k && k >= tin[a] + 1)
        return up[aux[k]];
    }
  }

  if (t != a) {
    int stkl[40], stkr[40], so = 0;
    for (; hld[a] != hld[t]; t = par[hld[t]])
      stkl[so] = tin[hld[t]], stkr[so] = tin[t], ++so;
    if (t != a)
      stkl[so] = tin[a] + 1, stkr[so] = tin[t], ++so;

    for (int i = so - 1; i >= 0; --i) {
      int l = stkl[i], r = stkr[i];
      cc = query(0, l - 1);
      k = search_leftmost(1, 0, N_ - 1, cc + 1);
      if (l <= k && k <= r)
        return up[aux[k]];
    }
  }
  return 0;
}

int cur, z = 0, call = 0;

void go(int t) {
  if (++call == 2000) {
    __builtin_trap();
    puts("-1");
    exit(0);
  }
  if (cur == t)
    return;
  int k;

  while ((k = find_key(cur, t))) {
    go(k);
    int unlock = query_path(cur, uu[k], NULL) ? vv[k] : uu[k];

    go(unlock);
    add(tin[upper(k)], -1);
  }
  z += dist(cur, t);
  cur = t;
}

int main() {
  scanf("%d%d%d", &n, &s, &t);
  for (int u, v, w, i = 1; i < n; ++i) {
    scanf("%d%d%d", &u, &v, &w), pus(u, v), pus(u, w), pus(v, u), pus(v, w);
    if (w)
      uu[w] = u, vv[w] = v;
  }

  dfs(1, 1);
  efs(1, 1);

  for (int i = 1; i <= n; ++i)
    if (up[i])
      add(tin[i], 1);

  cur = s;

  go(t);
  printf("%d", z);
}

Compilation message

Main.c: In function 'pus':
Main.c:46:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   46 |   else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                      ~~^~~
Main.c: In function 'main':
Main.c:155:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   scanf("%d%d%d", &n, &s, &t);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:157:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%d%d%d", &u, &v, &w), pus(u, v), pus(u, w), pus(v, u), pus(v, w);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 22876 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 27 ms 32000 KB Output is correct
4 Correct 27 ms 32084 KB Output is correct
5 Correct 28 ms 32092 KB Output is correct
6 Correct 27 ms 32036 KB Output is correct
7 Correct 27 ms 32336 KB Output is correct
8 Correct 27 ms 32084 KB Output is correct
9 Correct 27 ms 32292 KB Output is correct
10 Correct 27 ms 32232 KB Output is correct
11 Correct 29 ms 32080 KB Output is correct
12 Correct 24 ms 33116 KB Output is correct
13 Incorrect 25 ms 34524 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

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

Subtask #3
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 22876 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 27 ms 32000 KB Output is correct
4 Correct 27 ms 32084 KB Output is correct
5 Correct 28 ms 32092 KB Output is correct
6 Correct 27 ms 32036 KB Output is correct
7 Correct 27 ms 32336 KB Output is correct
8 Correct 27 ms 32084 KB Output is correct
9 Correct 27 ms 32292 KB Output is correct
10 Correct 27 ms 32232 KB Output is correct
11 Correct 29 ms 32080 KB Output is correct
12 Correct 24 ms 33116 KB Output is correct
13 Incorrect 25 ms 34524 KB Output isn't correct
14 Halted 0 ms 0 KB -