CSES - Planet Queries I

Debugging Help
#1

Problem Info

I was solving CSES - Planet Queries I. This requires binary lifting, which is exactly what I did.

My Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+5;
const int LG = 35;  // line 5
int n, q, up[LG][N];  // up is sparse table

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

    // take in input
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        up[0][i] = p;
    }

    // init sparse table
    for(int i = 1; i < LG; i++)
        for(int j = 1; j <= n; ++j)
            up[i][j] = up[i-1][up[i-1][j]];

    // solve queries
    while(q--){
        int x, k;
        cin >> x >> k;
        for(int i = 0; i < LG; ++i)
            if((k>>i)&1) {  // Line 29
                x = up[i][x];
            }
        cout << x << '\n';
    }
}

My code is simple enough: just do binary lifting.

Question

I submitted the above code, and I got WA. This was very weird, so I changed Line 5 of the above code to const int LG = 31 instead. For some reasons, it now works. Why did that happen? I suspect it’s Line 29’s fault.

#2

This is because you are using integers. Line 29 is doing k >> i with i = 34 but k is a 32bits integers so this makes line 29 UB I guess

#3

this makes line 29 UB I guess

What do you mean by 29 UB?

#4