oj.uz

Submission #24100

# Submission time Handle Problem Language Result Execution time Memory
24100 2017-05-31T00:37:13 Z jiaqiyang Railway Trip (JOI17_railway_trip) C++14
0 / 100
 206 ms 22356 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 16020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 22356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 22224 KB Output isn't correct
2 Halted 0 ms 0 KB -