Problem Info
I was doing Cow Land from USACO 2019
http://www.usaco.org/index.php?page=viewproblem2&cpid=921
What happened, and how I tried to understand what was going on (and failed)
This is my compile & run code, for reference:
g++ -Wall -Wshadow -Wextra -O2 -fsanitize=address,undefined -std=c++17 $file_name -o $file_base_name && /usr/bin/time -v timeout 10s ./$file_base_name
Once I finished writing, I tested code with sample test case and it worked correctly.
When I submitted my code, it got the MLE/RTE error; I initially thought it was strange, but I looked back at my code in search of overflows or something bad. I didn’t find anything, so I tried submitting just the very first line of code, so that the program would just declare the global arrays and do nothing in the main. It got the same error (I was very confused at this point. I thought “Is this really MLE?”).
At this point I tried something strange: I resubmitted without the “binlift” array (see code), since that is the biggest array I declare. And the error disappeared. I am therefore very confused on what is going on, since I don’t understand how an array of size 4 * 100100 * 26 = 13613600 bites (around 13 mb) can result in MLE. I am probably missing something, but I don’t know what to look for.
My Work
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ll long long
#define nl '\n'
const int N = 100100, K = 26;
int n, q, timer=0, d[N], a[N], tin[N], tout[N], t[2*N], parent[N];
// The array I was talking about
int binlift[K][N];
vector<int> adj[N];
void dfs(int s=0, int e=0) {
tin[s] = timer;
parent[s] = e;
t[n+timer] = t[n+tin[e]] ^ a[s];
timer++;
for (int node:adj[s]) {
if (node==e) continue;
d[node] = d[s] + 1;
dfs(node,s);
}
tout[s] = timer-1;
}
int lca(int i, int j) {
if (d[i] > d[j]) swap(i, j);
int distance = d[j] - d[i];
for (int Z = 25; Z >= 0; Z--) {
if (1 << Z <= distance) {
j = binlift[Z][j];
distance -= 1 << Z;
}
}
// Same level
for (int Z = 25; Z >= 0; Z--) {
if (binlift[Z][i] != binlift[Z][j]) {
i = binlift[Z][i];
j = binlift[Z][j];
}
}
int myLCA = parent[i];
if (i == j) myLCA = i;
return myLCA;
}
void preprocess() {
for (int i=0;i<n;i++) {
binlift[0][i] = parent[i];
}
for (int jmp = 1; jmp < K; jmp++) {
for (int i=0;i<n;i++) {
binlift[jmp][i] = binlift[jmp-1][binlift[jmp-1][i]];
}
}
}
int query(int p) { // set value at position p
int res = t[p+=n];
for (; p > 1; p >>= 1) res ^= t[p>>1];
return res;
}
void upd(int l, int r, int v) { // interval [l, r)
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) t[l++] ^= v;
if (r&1) t[--r] ^= v;
}
}
int main() {
freopen("cowland.in", "r", stdin);
freopen("cowland.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) { cin >> a[i]; }
for (int i = 0, s, e; i < n-1; i++) {
cin >> s >> e; s--; e--;
adj[s].pb(e);
adj[e].pb(s);
}
dfs(); preprocess();
while(q--) {
int which; cin >> which;
if (which == 1) {
int i,j; cin >> i >> j; i--;
upd(tin[i], tout[i]+1, a[i]);
a[i] = j;
upd(tin[i], tout[i]+1, a[i]);
} else {
int i,j; cin >> i >> j; i--; j--;
int ans1 = query(tin[i]), ans2 = query(tin[j]), curr_lca = lca(i,j);
int ans = (ans1^ans2)^a[curr_lca];
cout << ans << nl;
}
}
}
I think code is pretty clear, I just create graph with values, then I dfs to get euler tour and segment tree set up; I then process binary lifting array to later get LCA in O(logN). I then answer queries with segtree.