Company Queries II

#include <iomanip>
#include <iostream>
// #include <queue>
#include <vector>
#define ll long long

struct Emp {
  ll bossNum;
  ll height;
};
struct Qq {
  ll q0;
  ll q1;
};
std::ostream &operator<<(std::ostream &os, const std::vector<Qq> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << "(";
    os << v[i].q0;
    os << ", ";
    os << v[i].q1;
    os << ")";
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

std::ostream &operator<<(std::ostream &os, const std::vector<Emp> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << v[i].bossNum;
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

void printMap(std::vector<ll> &parentMap, ll empCount, ll logHeight) {
  for (int hh = 0; hh < logHeight; hh++) {
    for (int ee = 0; ee < empCount; ee++) {
      std::cout << std::setw(2) << parentMap[ee + hh * empCount] << " ";
    }
    std::cout << std::endl;
  }
}

ll run(ll q0, ll q1, std::vector<ll> &bosses, std::vector<ll> &heights) {
  ll ret = -2;
  if (q0 == q1) {
    ret = q0;
  } else if (heights[q0] == heights[q1]) {
    if (bosses[q0] == bosses[q1]) {
      ret = bosses[q0];
    } else {
      q0 = bosses[q0];
      q1 = bosses[q1];
    }
  } else if (heights[q0] > heights[q1]) {
    if (bosses[q0] == q1) {
      ret = q1;
    } else {
      q0 = bosses[q0];
      q1 = q1;
    }
  } else {
    if (q0 == bosses[q1]) {
      ret = q0;
    } else {
      q0 = q0;
      q1 = bosses[q1];
    }
  }
  if (ret == -2) {
    ret = run(q0, q1, bosses, heights);
  }
  return ret;
}

int main() {
  ll empCount, qCount;
  std::cin >> empCount;
  std::cin >> qCount;

  // std::vector<Emp> inputNums(empCount, {-1, -1});
  std::vector<ll> bosses(empCount, -1);
  std::vector<ll> heights(empCount, -1);
  bosses[0] = 0;

  for (ll ii = 0; ii < empCount - 1; ii++) {
    ll boss;
    std::cin >> boss;
    bosses[ii + 1] = boss - 1;
  }

  std::cerr << "Starting to create heightMap" << std::endl;
  for (ll ii = 0; ii < empCount; ii++) {
    ll kk = ii;
    ll hh = 0;
    while (kk != 0) {
      kk = bosses[kk];
      if (heights[kk] != -1) {
        hh += heights[kk] + 1;
        break;
      }
      hh += 1;
    }
    heights[ii] = hh;
  }
  std::cerr << "Stopped to creating heightMap" << std::endl;

  std::vector<std::pair<ll, ll>> queryes(qCount);
  for (ll ii = 0; ii < qCount; ii++) {
    ll q0;
    ll q1;
    std::cin >> q0;
    std::cin >> q1;
    queryes[ii].first = q0 - 1;  // (q0 < q1) ? (q0 - 1) : (q1 - 1);
    queryes[ii].second = q1 - 1; // (q0 < q1) ? (q1 - 1) : (q0 - 1);
  }
  std::cerr << "started " << qCount << std::endl;
  for (int ii = 0; ii < qCount; ii++) {
    ll q0 = queryes[ii].first;
    ll q1 = queryes[ii].second;
    std::cout << run(q0, q1, bosses, heights) + 1 << std::endl;
    if (ii % (qCount / 10) == 0) {
      std::cerr << ii << std::endl;
    }
  }
}

Test 1

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 10
0
1
2
3
4
5
6
7
8
9

Test 2

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 10
0
1
2
3
4
5
6
7
8
9

Test 3

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 10
0
1
2
3
4
5
6
7
8
9

Test 4

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 10
0
1
2
3
4
5
6
7
8
9

Test 5

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 10
0
1
2
3
4
5
6
7
8
9

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 200000
0
20000
40000
60000
80000
100000
120000
140000
160000
180000

Test 8

Verdict: ACCEPTED

Starting to create heightMap
Stopped to creating heightMap
started 200000
0
20000
40000
60000
80000
100000
120000
140000
160000
180000

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: RUNTIME ERROR

Starting to create heightMap
Stopped to creating heightMap
started 4

Test 12

Verdict: TIME LIMIT EXCEEDED