Submission #582760

#	Time	Username	Problem	Language	Result	Execution time	Memory
582760		AlexLuchianov	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	482 ms	82460 KiB

railway_trip

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>

using ll = long long;

int const nmax = 100000;
int const lgmax = 20;
int rmq[1 + lgmax][1 + nmax], rmq2[1 + lgmax][1 + nmax];
int v[5 + nmax];

void computeRmq(int n) {
  for(int i = 1;i <= n; i++)
    rmq[0][i] = i;
  auto bestOf = [&](int x, int y) {
    if(v[x] <= v[y])
      return y;
    else
      return x;
  };
  for(int h = 1; h <= lgmax; h++)
    for(int i = 1; i <= n - (1 << h) + 1; i++)
      rmq[h][i] = bestOf(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
}

void computeRmq2(int n) {
  for(int i = 1;i <= n; i++)
    rmq2[0][i] = i;
  auto bestOf = [&](int x, int y) {
    if(v[x] < v[y])
      return y;
    else
      return x;
  };
  for(int h = 1; h <= lgmax; h++)
    for(int i = 1; i <= n - (1 << h) + 1; i++)
      rmq2[h][i] = bestOf(rmq2[h - 1][i], rmq2[h - 1][i + (1 << (h - 1))]);
}

int extract(int x, int y) {
  if(y < x)
    return 0;
  auto lg = [&](int n) {
    return 31 - __builtin_clz(n);
  };
  int h = lg(y - x + 1);
  auto bestOf = [&](int x, int y) {
    if(v[x] <= v[y])
      return y;
    else
      return x;
  };
  
  return bestOf(rmq[h][x], rmq[h][y - (1 << h) + 1]);
}
int extract2(int x, int y) {
  if(y < x)
    return 0;
  auto lg = [&](int n) {
    return 31 - __builtin_clz(n);
  };
  int h = lg(y - x + 1);
  auto bestOf = [&](int x, int y) {
    if(v[x] < v[y])
      return y;
    else
      return x;
  };
  
  return bestOf(rmq2[h][x], rmq2[h][y - (1 << h) + 1]);
}

std::vector<int> tree[5 + nmax], g[5 + nmax];
std::vector<int> spec[5 + nmax];

void addEdge(int x, int y) {
  if(0 < x && 0 < y) {
    g[x].push_back(y);
    g[y].push_back(x);
  }
}

void addTreeEdge(int x, int y) {
  if(0 < x && 0 < y) {
    //std::cout << "Tree: " << x << " " << y << '\n';
    tree[x].push_back(y);
    tree[y].push_back(x);
  }
}

void addSpec(int x, int y) {
  if(0 < x && 0 < y) {
    spec[x].push_back(y);
  }
}

void buildTree(int from, int to, int left, int right, int father) {
  if(from <= to) {
    int node;
    if(left == father)
      node = extract2(from, to);
    else
      node = extract(from, to);

    if(0 < left && v[extract(left + 1, node - 1)] != v[node]) {
      addEdge(left, node);
    }
    if(0 < right && v[extract(node + 1, right - 1)] != v[node]) {
      addEdge(right, node);
    }
      addSpec(node, left);
      addSpec(node, right);
    
    if(father < node)
      assert(v[extract(father + 1, node - 1)] < v[node]);
    else
      assert(v[extract(node + 1, father - 1)] < v[node]);
    
    addTreeEdge(father, node);
    buildTree(from, node - 1, left, node, node);
    buildTree(node + 1, to, node, right, node);
  }
}

int seen[5 + nmax], sz[5 + nmax];
int level[5 + nmax], touched[5 + nmax];
int timestamp = 0;

void computesz(int node, int parent) {
  sz[node] = 1;
  touched[node] = timestamp;
  for(int h = 0; h < tree[node].size(); h++) {
    int to = tree[node][h];
    if(to != parent && seen[to] == 0) {
      computesz(to, node);
      sz[node] += sz[to];
    }
  }
}

int getCentroid(int node, int parent, int target) {
  for(int h = 0; h < tree[node].size(); h++) {
    int to = tree[node][h];
    if(parent != to && seen[to] == 0 && target <= sz[to])
      return getCentroid(to, node, target);
  }
  return node;
}

int dist[1 + lgmax * 3][5 + nmax], fromWho[1 + lgmax * 3][5 + nmax];


void computeDist(int start, int level) {
  if(touched[start] != timestamp)
    return ;
  std::queue<int> q;
  q.push(start);
  dist[level][start] = 0;
  while(0 < q.size()) {
    int node = q.front();
    fromWho[level][node] = start;
    q.pop();
    for(int h = 0; h < g[node].size(); h++) {
      int to = g[node][h];
      if(touched[to] == timestamp && dist[level][node] + 1 < dist[level][to]) {
        dist[level][to] = dist[level][node] + 1;
        q.push(to);
      }
    }
  }
}

void solve(int root, int level) {
  ++timestamp;
  computesz(root, 0);
  int centroid = getCentroid(root, 0, sz[root] / 2);
  computeDist(centroid, level++);
  for(int h = 0; h < spec[centroid].size(); h++) {
    computeDist(spec[centroid][h], level++);
  }

  seen[centroid] = 1;
  for(int h = 0; h < tree[centroid].size(); h++) {
    int to = tree[centroid][h];
    if(seen[to] == 0)
      solve(to, level);
  }
}

void resetDist(int n) {
  for(int i = 0; i <= lgmax * 3; i++)
    for(int j = 1; j <= n; j++)
      dist[i][j] = nmax * 2;
}

int brute(int x, int y) {
  std::queue<int> q;
  q.push(x);
  std::vector<int> newdist(1 + nmax, nmax * 2), prev(1 + nmax);
  newdist[x] = 0;
  while(0 < q.size()) {
    int node = q.front();
    q.pop();
    for(int h = 0; h < g[node].size(); h++) {
      int to = g[node][h];
      if(newdist[to] == nmax * 2) {
        newdist[to] = newdist[node] + 1;
        prev[to] = node;
        q.push(to);
      }
    }
  }
  int target =y ;
  return newdist[y] - 1;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, k, q;
  std::cin >> n >> k >> q;
  for(int i = 1; i <= n; i++)
    std::cin >> v[i];
  computeRmq(n);
  computeRmq2(n);
  buildTree(1, n, 0, 0, 0);
  resetDist(n);
  solve(1, 0);
  
  for(int i = 1; i <= q; i++) {
    int x, y;
    std::cin >> x >> y;
    int result = nmax * 2;
    for(int h = 0; h <= lgmax * 3; h++) {
      if(fromWho[h][x] == fromWho[h][y])
        result = std::min(result, dist[h][x] + dist[h][y] - 1);
    }
    std::cout << result << '\n';
  }
  return 0;
}

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