oj.uz

Submission #582760

# Submission time Handle Problem Language Result Execution time Memory
582760 2022-06-24T11:41:50 Z AlexLuchianov Railway Trip (JOI17_railway_trip) C++14
100 / 100
 482 ms 82460 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7892 KB Output is correct
2 Correct 4 ms 7892 KB Output is correct
3 Correct 4 ms 7892 KB Output is correct
4 Correct 4 ms 7892 KB Output is correct
5 Correct 4 ms 7892 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7892 KB Output is correct
8 Correct 5 ms 7904 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8404 KB Output is correct
2 Correct 270 ms 71140 KB Output is correct
3 Correct 286 ms 71060 KB Output is correct
4 Correct 276 ms 71360 KB Output is correct
5 Correct 255 ms 71436 KB Output is correct
6 Correct 287 ms 71128 KB Output is correct
7 Correct 262 ms 71756 KB Output is correct
8 Correct 176 ms 78624 KB Output is correct
9 Correct 232 ms 76296 KB Output is correct
10 Correct 193 ms 77000 KB Output is correct
11 Correct 299 ms 76540 KB Output is correct
12 Correct 258 ms 76472 KB Output is correct
13 Correct 287 ms 76396 KB Output is correct
14 Correct 255 ms 76548 KB Output is correct
15 Correct 261 ms 76540 KB Output is correct
16 Correct 258 ms 76436 KB Output is correct
17 Correct 267 ms 72064 KB Output is correct
18 Correct 252 ms 72396 KB Output is correct
19 Correct 172 ms 72524 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 71380 KB Output is correct
2 Correct 428 ms 71568 KB Output is correct
3 Correct 425 ms 71484 KB Output is correct
4 Correct 444 ms 72800 KB Output is correct
5 Correct 413 ms 72824 KB Output is correct
6 Correct 464 ms 72672 KB Output is correct
7 Correct 434 ms 72704 KB Output is correct
8 Correct 359 ms 74660 KB Output is correct
9 Correct 371 ms 80416 KB Output is correct
10 Correct 390 ms 80328 KB Output is correct
11 Correct 362 ms 80392 KB Output is correct
12 Correct 351 ms 80316 KB Output is correct
13 Correct 329 ms 80472 KB Output is correct
14 Correct 331 ms 72844 KB Output is correct
15 Correct 357 ms 73120 KB Output is correct
16 Correct 447 ms 73400 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 71716 KB Output is correct
2 Correct 481 ms 72060 KB Output is correct
3 Correct 464 ms 73192 KB Output is correct
4 Correct 399 ms 73336 KB Output is correct
5 Correct 353 ms 80360 KB Output is correct
6 Correct 366 ms 77948 KB Output is correct
7 Correct 397 ms 77944 KB Output is correct
8 Correct 341 ms 78704 KB Output is correct
9 Correct 444 ms 78124 KB Output is correct
10 Correct 482 ms 78096 KB Output is correct
11 Correct 451 ms 78272 KB Output is correct
12 Correct 429 ms 78172 KB Output is correct
13 Correct 478 ms 78256 KB Output is correct
14 Correct 464 ms 80620 KB Output is correct
15 Correct 435 ms 81316 KB Output is correct
16 Correct 445 ms 82460 KB Output is correct
17 Correct 426 ms 78852 KB Output is correct
18 Correct 433 ms 78468 KB Output is correct
19 Correct 460 ms 78756 KB Output is correct
20 Correct 401 ms 74444 KB Output is correct
21 Correct 468 ms 73540 KB Output is correct
22 Correct 417 ms 73532 KB Output is correct
23 Correct 366 ms 74308 KB Output is correct