Submission #24100

#	Time	Username	Problem	Language	Result	Execution time	Memory
24100		jiaqiyang	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	206 ms	22356 KiB

railway_trip

#include <cstdio>
#include <vector>
#include <algorithm>

const int N = 200000 + 10;

int n, k, q, tot, a[N];
std::vector<int> adj[N];

int pred[N], succ[N];

int anc[N];

int find(int x) { return anc[x] == x ? x : (anc[x] = find(anc[x])); }

void link(int x, int y) {
  anc[find(x)] = find(y);
  adj[x].push_back(y);
  adj[y].push_back(x);
}

void init() {
  static int stk[N];
  int top = 0;
  for (int i = 1; i <= n; ++i) {
    for (; top && a[stk[top]] < a[i]; --top) succ[stk[top]] = i;
    stk[++top] = i;
  }
  top = 0;
  for (int i = n; i > 0; --i) {
    for (; top && a[stk[top]] < a[i]; --top) pred[stk[top]] = i;
    stk[++top] = i;
  }
  static std::pair<int, int> info[N];
  for (int i = 1; i <= n; ++i) info[i] = std::make_pair(a[i], i);
  std::sort(info + 1, info + n + 1);
  for (int i = 1; i <= 2 * n; ++i) anc[i] = i;
  for (int i = 1; i <= n; ++i) {
    int x = info[i].second, c = x + n, y = pred[x], z = succ[x];
    link(x, c);
    if (y && find(x) != find(y)) link(y, c);
    if (z && find(x) != find(z)) link(z, c);
  }
}

int fa[N], dep[N], size[N], son[N], top[N];

void bfs() {
  static int q[N];
  q[1] = dep[1] = 1;
  for (int i = 1, r = 1; i <= r; ++i) {
    int a = q[i];
    for (int j = 0; j < adj[a].size(); ++j) {
      int b = adj[a][j];
      if (b != fa[a]) fa[q[++r] = b] = a, dep[b] = dep[a] + 1;
    }
  }
  for (int i = 1; i <= 2 * n; ++i) size[i] = 1;
  for (int i = 2 * n; i > 1; --i) size[fa[q[i]]] += size[q[i]];
  for (int i = 2; i <= 2 * n; ++i) if (size[i] > size[son[fa[i]]]) son[fa[i]] = i;
  for (int i = 1; i <= 2 * n; ++i) {
    int a = q[i];
    if (top[a]) continue;
    for (int b = a; b; b = son[b]) top[b] = a;
  }
}

int lca(int x, int y) {
  for (; top[x] != top[y]; x = fa[top[x]]) if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
  return dep[x] < dep[y] ? x : y;
}

inline int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }

int main() {
  scanf("%d%d%d", &n, &k, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  init();
  bfs();
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", dist(x, y) / 2 - 1);
  }
  return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:76:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &k, &q);
                              ^
railway_trip.cpp:77:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                  ^
railway_trip.cpp:82:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
                          ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55