oj.uz

답안 #1043590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043590 2024-08-04T11:47:56 Z sleepntsheep LOSTIKS (INOI20_lostiks) C
0 / 100
 32 ms 34396 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 (tin[s] >= k && 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 (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);
      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 22876 KB Output is correct
3 Correct 31 ms 32140 KB Output is correct
4 Correct 32 ms 32164 KB Output is correct
5 Correct 29 ms 32192 KB Output is correct
6 Correct 30 ms 32028 KB Output is correct
7 Correct 29 ms 32208 KB Output is correct
8 Correct 29 ms 32080 KB Output is correct
9 Correct 28 ms 32380 KB Output is correct
10 Correct 29 ms 32076 KB Output is correct
11 Correct 27 ms 32084 KB Output is correct
12 Correct 23 ms 33108 KB Output is correct
13 Incorrect 25 ms 34396 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 22872 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 31 ms 32140 KB Output is correct
4 Correct 32 ms 32164 KB Output is correct
5 Correct 29 ms 32192 KB Output is correct
6 Correct 30 ms 32028 KB Output is correct
7 Correct 29 ms 32208 KB Output is correct
8 Correct 29 ms 32080 KB Output is correct
9 Correct 28 ms 32380 KB Output is correct
10 Correct 29 ms 32076 KB Output is correct
11 Correct 27 ms 32084 KB Output is correct
12 Correct 23 ms 33108 KB Output is correct
13 Incorrect 25 ms 34396 KB Output isn't correct
14 Halted 0 ms 0 KB -