I was solving this Problem Link and encountered a bug. I'm getting WA on test 10, but I run stress test locally on my PC and didn't found any counter test cases. Please take a look on my code.
Approach that I used to solve this problem
Here are my code.
Test Case Generator
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100;
int main(int argc, char* argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
mt19937_64 rnd(atoi(argv[1]));
auto next = [&](ll x) {
return rnd() % x;
};
auto randRange = [&](ll a, ll b) {
return a + rnd() % (b - a + 1);
};
int n = randRange(2, N);
int q = randRange(1, N);
cout << n << " " << q << "\n";
for(int i = 0; i < n; ++i)
cout << randRange(0, 2147483647) << " \n"[i == n - 1];
vector<int> a(1), b(n - 1);
iota(b.begin(), b.end(), 1);
random_shuffle(b.begin(), b.end(), next);
while(!b.empty()) {
int u = a[next((int) a.size())];
int v = b.back();
if(next(2) == 1)
swap(u, v);
cout << u + 1 << " " << v + 1 << "\n";
a.push_back(b.back());
b.pop_back();
}
for(int i = 0; i < q; ++i)
cout << randRange(1, n) << " " << randRange(1, n) << "\n";
return 0;
}
Brute force solution
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char* argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(auto& x : a)
cin >> x;
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> parent(n);
vector<int> depth(n);
function<void(int, int)> dfs = [&](int u, int p) {
parent[u] = p;
depth[u] = (u == 0 ? 0 : depth[p] + 1);
for(int& v : adj[u]) {
if(v == p)
continue;
dfs(v, u);
}
};
dfs(0, -1);
while(q--) {
int u, v;
cin >> u >> v;
--u, --v;
if(depth[u] < depth[v])
swap(u, v);
set<int> s;
s.insert(a[u]);
s.insert(a[v]);
while(depth[u] > depth[v]) {
u = parent[u];
s.insert(a[u]);
}
while(u != v) {
u = parent[u];
v = parent[v];
s.insert(a[u]);
s.insert(a[v]);
}
cout << s.size() << "\n";
}
return 0;
}
My submission
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char* argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(auto& x : a)
cin >> x;
vector<int> b(a);
sort(b.begin(), b.end());
for(auto& x : a)
x = lower_bound(b.begin(), b.end(), x) - b.begin();
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vector<int>> dp(n, vector<int>(20));
vector<int> depth(n);
vector<int> in(n), out(n);
vector<int> order;
order.reserve(n * 2);
function<void(int, int)> dfs = [&](int u, int p) {
dp[u][0] = (u == 0 ? 0 : p);
depth[u] = (u == 0 ? 0 : depth[p] + 1);
in[u] = (int) order.size();
order.push_back(u);
for(int& v : adj[u])
if(v != p)
dfs(v, u);
out[u] = (int) order.size();
order.push_back(u);
};
dfs(0, -1);
for(int x = 1; x < 20; ++x)
for(int i = 0; i < n; ++i)
dp[i][x] = dp[dp[i][x - 1]][x - 1];
auto lift = [&](int u, int step) -> int {
int r = 0;
while(step) {
if(step & 1)
u = dp[u][r];
step >>= 1;
r <<= 1;
}
return u;
};
auto lca = [&](int x, int y) -> int {
if(depth[x] < depth[y])
swap(x, y);
x = lift(x, depth[x] - depth[y]);
if(x == y)
return x;
for(int i = 19; i >= 0; --i) {
int new_x = dp[x][i];
int new_y = dp[y][i];
if(new_x != new_y) {
x = new_x;
y = new_y;
}
}
assert(dp[x][0] == dp[y][0]);
return dp[x][0];
};
vector<tuple<int, int, int, int>> qry(q);
for(int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
if(depth[u] > depth[v])
swap(u, v);
int z = lca(u, v);
if(u == z)
qry[i] = {in[u], in[v], -1, i};
else
qry[i] = {out[u], in[v], z, i};
}
const int m = sqrt(n * 2) + 1;
sort(qry.begin(), qry.end(), [&](const tuple<int, int, int, int>& x, const tuple<int, int, int, int>& y) {
if(get<0>(x) / m == get<0>(y) / m)
return (get<0>(x) / m & 1 ? get<1>(x) > get<1>(y) : get<1>(x) < get<1>(y));
return get<0>(x) < get<0>(y);
});
vector<int> occurrence(n);
vector<int> cnt((int) b.size());
int counter = 0;
auto add = [&](int u) {
++occurrence[u];
if(occurrence[u] % 2 == 0) {
--cnt[a[u]];
if(cnt[a[u]] == 0)
--counter;
} else {
++cnt[a[u]];
if(cnt[a[u]] == 1)
++counter;
}
};
auto remove = [&](int u) {
--occurrence[u];
if(occurrence[u] % 2 == 0) {
--cnt[a[u]];
if(cnt[a[u]] == 0)
--counter;
} else {
++cnt[a[u]];
if(cnt[a[u]] == 1)
++counter;
}
};
vector<int> ans(q);
int l = 0, r = 0;
add(order[0]);
for(int i = 0; i < q; ++i) {
int L, R, z, id;
tie(L, R, z, id) = qry[i];
while(l < L) {
remove(order[l]);
++l;
}
while(l > L) {
--l;
add(order[l]);
}
while(r < R) {
++r;
add(order[r]);
}
while(r > R) {
remove(order[r]);
--r;
}
if(z != -1)
add(z);
ans[id] = counter;
if(z != -1)
remove(z);
}
for(auto& x : ans)
cout << x << "\n";
return 0;
}
EDIT: SOLVED. Stupid mistake in binary lifting function.
Notice that if it seems you get WA on the last test in SPOJ, you may get WA on any test before, not just test case 10.
I found your mistake:
In lambda
auto lift = [&](int u, int step) -> int(line 59), you should replacer <<= 1;forr++;, asdp[i][j]means the $$$2^j$$$ -th father of node $$$i$$$.AC submission 29145844.
Thanks. That's a stupid mistake made by me. It worked.
It is strange that stress test didn't find this bug.