Company Queries II

input/code.cpp: In function 'int ancestor(int, int)':
input/code.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int ind=0; ind<ancestors[node].size(); ind++) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~~

#include <vector>
#include <iostream>
#include <math.h>
using namespace std;

vector<vector<int>> ancestors;  // a[node][lb(x)]
vector<int> depth;
vector<bool> been;
vector<int> dfsOrder;
vector<int> boss;

int dfs(int node) {
    if (been[node]) return depth[node];
    been[node] = true;
    if (node == 0) return depth[node];
    int d = dfs(boss[node]) + 1;
    dfsOrder.push_back(node);
    depth[node] = d;
    return d;
}

int ancestor(int node, int up) {
    for (int ind=0; ind<ancestors[node].size(); ind++) {
        if ((1 << ind) & up) {
            node = ancestors[node][ind];
        }
    }
    return node;
}

int main() {
    int n, q;
    cin >> n >> q;
    ancestors.resize(n);
    depth.resize(n);
    been.resize(n);
    dfsOrder.resize(0);
    boss.resize(n);
    for (int i=0; i<n; i++) { been[i] = false; }

    boss[0] = 0;
    depth[0] = 0;
    dfsOrder.push_back(0);
    
    int a, b;
    for (int i=1; i<n; i++) {
        cin >> b;
        b--;
        boss[i] = b;
    }

    for (int i=0; i<n; i++) { dfs(i); }

    int logN = log2(2*n);
    
    // set ancestors
    for (int i=0; i<n; i++) { ancestors[i].push_back(boss[i]); }
    for (int i=0; i<logN; i++) {
        for (int j=0; j<n; j++) {
            ancestors[dfsOrder[j]].push_back(ancestors[ancestors[dfsOrder[j]][i]][i]);
        }
    }
    int da, db;
    for (int i=0; i<q; i++) {
        cin >> a >> b;
        a--; b--;
        da = depth[a];
        db = depth[b];
        if (da > db) swap(a, b);  // b is lower
        b = ancestor(b, abs(da - db));  // level

        // binary search
        int k = 0;
        for (int up = n/2; up >= 1; up /= 2) {
            while (k+up < n && (ancestor(a, k+up) != ancestor(b, k+up))) k += up;
        }
        cout << ancestor(a, k + 1) + 1 << endl;
    }

    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: TIME LIMIT EXCEEDED