Header Ad

HackerEarth Xor tree problem solution

In this HackerEarth Xor tree problem solution You are given an undirected tree with N nodes. Every node is initially assigned a value equal to 0.

Perform Q queries that are given on the tree as follows:
  • u v w: For all the nodes present on a simple path between nodes u and v take the xor of node value with w. 

Find the sum of values assigned to all the nodes after performing Q queries.


HackerEarth Xor tree problem solution


HackerEarth Xor tree problem solution.

#include "bits/stdc++.h"
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
for ( \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
blockTime.second; \
debug("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
)
#ifdef LOCAL
#include "pprint.hpp"
#endif
#define endl '\n';
#define pb push_back
#define mod 1000000007
#define ll long long int
#define prn(x) cerr<<x<<endl;
#define all(x) x.begin(),x.end()
using namespace std;
#define test_case 1

const ll N = 25;
ll n, res, cnt, node;
vector<ll> A, dpt;
vector<vector<ll>> g, par;

void init(){
node=0;
A.assign(n+1,0);
dpt.assign(n+1,0);
g.assign(n+1,vector<ll>());
par.assign(n+1,vector<ll>(N+1,0));
}

void dfs(ll s, ll p){
++node;
par[s][0]=p;
for(int i=1;i<N;++i)
par[s][i]=par[par[s][i-1]][i-1];
for(auto x:g[s]){
if(x==p) continue;
dpt[x] = 1 + dpt[s];
dfs(x, s);
}
}

ll lca(ll u, ll v){
ll diff = abs(dpt[v]-dpt[u]);
for(ll i=0;i<N;++i){
if((1LL<<i)&diff)
v = par[v][i];
}
if(u==v)
return u;
for(ll i = N-1;i>=0;--i){
if(par[u][i]==par[v][i])
continue;
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}

ll dfs2(ll s, ll p){
ll sum=0;
for(auto x:g[s]){
if(x==p) continue;
sum ^= dfs2(x,s);
}
A[s] ^= sum;
return A[s];
}

void solution(){
cin>>n;
assert(n>=1 && n<=100000);
ll q;
cin>>q;

init();
// set<pair<ll,ll>> s;
for(ll i=1;i<n;++i){
ll u, v;
cin>>u>>v;
assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
g[u].pb(v);
g[v].pb(u);
}

dfs(1,0);
assert(node==n);


assert(q>=1 && q<=100000);
for(ll i=1;i<=q;++i){
ll u, v, w;
cin>>u>>v>>w;
assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
assert(w>=0 && w<=1000000000);
if(dpt[u]>dpt[v])
swap(u,v);
ll lc = lca(u, v);
A[u] ^= w;
A[v] ^= w;
A[lc] ^= w;
A[par[lc][0]] ^= w;
}
dfs2(1, 0);
ll answer = 0;
for(int i = 1 ; i <= n ; i++){
answer += A[i];
}
cout << answer << endl;
}

int main(int argc, char *argv[])
{
#ifdef LOCAL
freopen("in.txt" , "r" , stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
#endif

int t=1;
if(test_case)
cin>>t;
assert(t>=1 && t<=5);
time__("Solution Time"){
while(t--){
solution();
}
}
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14, LG = 17;
int n, h[MAX_N], par[LG][MAX_N], a[MAX_N];
vector<int> g[MAX_N];

void dfs(int v = 0, int p = -1) {
for (int u : g[v])
if (u != p) {
par[0][u] = v;
h[u] = h[v] + 1;
dfs(u, v);
}
}

int lca(int v, int u) {
if (h[v] > h[u])
swap(v, u);
for (int i = 0; i < LG; i++)
if (h[u] - h[v] >> i & 1)
u = par[i][u];
for (int i = LG - 1; i >= 0; i--)
if (par[i][v] != par[i][u])
v = par[i][v], u = par[i][u];
return v == u ? v : par[0][v];
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int q;
cin >> n >> q;
fill(g, g + n, vector<int>());
fill(a, a + n, 0);
for (int i = 0; i < n - 1; i++) {
int v, u;
cin >> v >> u;
v--, u--;
g[v].push_back(u);
g[u].push_back(v);
}
dfs();
for (int k = 1; k < LG; k++)
for (int i = 0; i < n; i++)
par[k][i] = par[k - 1][par[k - 1][i]];
while (q--) {
int v, u, w;
cin >> v >> u >> w;
--v;
--u;
int p = lca(v, u);
while (v != p) {
a[v] ^= w;
v = par[0][v];
}
while (u != p) {
a[u] ^= w;
u = par[0][u];
}
a[p] ^= w;
}
cout << accumulate(a, a + n, 0ll) << '\n';
}
}

Post a Comment

0 Comments