Submission #1043591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043591		sleepntsheep	LOSTIKS (INOI20_lostiks)	C11	0 / 100	30 ms	34388 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41