oj.uz

답안 #1043587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043587 2024-08-04T11:46:27 Z sleepntsheep LOSTIKS (INOI20_lostiks) C
0 / 100
 31 ms 34392 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 == 200) {
    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 26 ms 32064 KB Output is correct
4 Correct 26 ms 32092 KB Output is correct
5 Correct 26 ms 32080 KB Output is correct
6 Correct 31 ms 32080 KB Output is correct
7 Correct 28 ms 32212 KB Output is correct
8 Correct 29 ms 32084 KB Output is correct
9 Correct 29 ms 32348 KB Output is correct
10 Correct 27 ms 32236 KB Output is correct
11 Correct 27 ms 32116 KB Output is correct
12 Correct 26 ms 32960 KB Output is correct
13 Incorrect 24 ms 34392 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 23012 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 26 ms 32064 KB Output is correct
4 Correct 26 ms 32092 KB Output is correct
5 Correct 26 ms 32080 KB Output is correct
6 Correct 31 ms 32080 KB Output is correct
7 Correct 28 ms 32212 KB Output is correct
8 Correct 29 ms 32084 KB Output is correct
9 Correct 29 ms 32348 KB Output is correct
10 Correct 27 ms 32236 KB Output is correct
11 Correct 27 ms 32116 KB Output is correct
12 Correct 26 ms 32960 KB Output is correct
13 Incorrect 24 ms 34392 KB Output isn't correct
14 Halted 0 ms 0 KB -