oj.uz

답안 #1043588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043588 2024-08-04T11:46:45 Z sleepntsheep LOSTIKS (INOI20_lostiks) C
0 / 100
 32 ms 34428 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 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 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 (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 cc, a = lca(s, t);
  if (s != a) {
    for (; hld[a] != hld[s]; s = par[hld[s]]) {
      cc = query(tin[s] + 1, n);
      int k = search_rightmost(1, 0, N_ - 1, cc + 1);
      if (k >= tin[hld[s]])
        return up[aux[k]];
    }
    if (s != a) {
      cc = query(tin[s] + 1, n);
      int k = search_rightmost(1, 0, N_ - 1, cc + 1);
      if (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);
      int k = search_leftmost(1, 0, N_ - 1, cc + 1);
      if (k >= l && k <= r) {
        return up[aux[k]];
      }
    }
  }
  return 0;
}

int cur, z = 0, call = 0;

void go(int t) {
  if (++call == 2000) {
    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:154:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   scanf("%d%d%d", &n, &s, &t);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:156:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     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 22872 KB Output is correct
2 Correct 2 ms 22872 KB Output is correct
3 Correct 29 ms 32076 KB Output is correct
4 Correct 28 ms 32088 KB Output is correct
5 Correct 27 ms 32112 KB Output is correct
6 Correct 27 ms 32040 KB Output is correct
7 Correct 27 ms 32244 KB Output is correct
8 Correct 26 ms 32124 KB Output is correct
9 Correct 32 ms 32348 KB Output is correct
10 Correct 28 ms 32136 KB Output is correct
11 Correct 27 ms 32148 KB Output is correct
12 Correct 23 ms 33116 KB Output is correct
13 Incorrect 23 ms 34428 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 22872 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 22872 KB Output is correct
2 Correct 2 ms 22872 KB Output is correct
3 Correct 29 ms 32076 KB Output is correct
4 Correct 28 ms 32088 KB Output is correct
5 Correct 27 ms 32112 KB Output is correct
6 Correct 27 ms 32040 KB Output is correct
7 Correct 27 ms 32244 KB Output is correct
8 Correct 26 ms 32124 KB Output is correct
9 Correct 32 ms 32348 KB Output is correct
10 Correct 28 ms 32136 KB Output is correct
11 Correct 27 ms 32148 KB Output is correct
12 Correct 23 ms 33116 KB Output is correct
13 Incorrect 23 ms 34428 KB Output isn't correct
14 Halted 0 ms 0 KB -