HackerEarth Tree queries problem solution

In this HackerEarth Tree queries problem solution You are given a tree T with N nodes rooted at 1. The ith node of the tree has been assigned the value Ai. You are required to handle two types of queries:

v x : Update the value of node v to x, that is Av = x.

v Consider the multiset of values of nodes present in the subtree of node v. Consider all non-empty subsets of this set. Alice and Bob play a game on each of these subsets (independently) in alternating turns.

For each subset, Alice starts the game. In each turn, the current player must choose some element of the current subset and reduce it to some non-negative element. The player who cannot make a move loses. Note that it is necessary to reduce or decrease the element.

You need to find the number of subsets where Bob is guaranteed to win. The number of subsets can be very large, output it modulo 10000000007(10^9 + 7)

HackerEarth Tree queries problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int mypower(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b%2)
            ans = ans*1ll*a%mod;
        b = b/2;
        a = a*1ll*a%mod;
    }
    return ans;
}
void dfs(vector<int> tree[], int v, int p, vector<int> &tour, int start[], int end[])
{
    tour.push_back(v);
    start[v] = tour.size();
    for(int j = 0 ; j < tree[v].size() ; j++)
        if(tree[v][j] != p)
            dfs(tree, tree[v][j] ,v, tour, start, end);
    end[v] = tour.size();
}
#define mxn 500005
int seg[4*mxn][20];
void insert_vec(int cur, int ele)
{
    int i;
    for(i=0;i<20;i++)
    {
        if((ele & (1 << i)) == 0)
            continue;
        if(!seg[cur][i])
        {
            seg[cur][i] = ele;
            return;
        }
        ele = (ele^seg[cur][i]);
    }
}
void build(int cur, int l, int r, int inv[], int arr[])
{
    if(l == r)
    {
        insert_vec(cur, arr[inv[l]]);
        return;
    }
    int mid = (l+r)/2;
    build(2*cur, l, mid, inv, arr);
    build(2*cur+1, mid+1, r, inv, arr);
    for(int i=0;i<20;i++)
        seg[cur][i] = seg[2*cur][i]; // update in ok, 1 - ok is same
    for(int i=0;i<20;i++)
        if(seg[2*cur + 1][i])
            insert_vec(cur, seg[2*cur+1][i]);
}
void update(int cur, int l, int r, int idx, int ele)
{
    if(l == r)
    {
        for(int i=0;i<20;i++)
            seg[cur][i] = 0;
        insert_vec(cur, ele);
        return;    
    }
    int mid = (l+r)/2;
    int ok = -1;
    if(idx <= mid)
        update(2*cur, l, mid, idx, ele), ok = 0;
    else
        update(2*cur+1, mid+1, r, idx, ele), ok = 1;
    for(int i=0;i<20;i++)
        seg[cur][i] = seg[2*cur + 1 - ok][i];
    for(int i=0;i<20;i++)
        if(seg[2*cur + ok][i])
            insert_vec(cur, seg[2*cur+ok][i]);
}
vector<int> query(int cur, int l, int r, int ql, int qr)
{
    if(ql > r || qr < l)
    {
        vector<int> vec(20);
        return vec;
    }
    if(l >= ql && r <= qr)
    {
        vector<int> vec(20);
        for(int i=0;i<20;i++)
            vec[i] = seg[cur][i];
        return vec;
    }
    int mid = (l+r)/2;
    if(ql > mid)
        return query(2*cur+1, mid+1, r, ql, qr);
    if(qr <= mid)
        return query(2*cur, l, mid, ql, qr);
    vector<int> left = query(2*cur, l, mid, ql, qr);
    vector<int> right = query(2*cur+1, mid+1, r, ql, qr);
    for(int j = 0; j < 20; j++)
        if(right[j])
        {
            int ele = right[j];
            for(int i = 0; i < 20; i++)
            {
                if((ele & (1 << i)) == 0)
                    continue;
                if(!left[i])
                {
                    left[i] = ele;
                    break;
                }
                ele = (ele^left[i]);
            }
        }
    return left;
}
int main() {
    // your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    assert(1 <= t && t <= 10000);
    while(t--)
    {
        int n, q;
        cin >> n;
        int arr[n+1];
        vector<int> tree[n+1];
        int i;
        for(i=1;i<=n;i++)
            cin >> arr[i];
        for(i=1;i<n;i++)
        {
            int x, y;
            cin >> x >> y;
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        vector<int> tour;
        int start[n+1] = {0}, end[n+1] = {0};
        dfs(tree, 1, 0, tour, start, end);
        int inv[n+1] = {0};
        for(i=1;i<=n;i++)
            inv[start[i]] = i;
        build(1, 1, n, inv, arr);
        cin >> q;
        while(q--)
        {
            int tp;
            cin >> tp;
            if(tp == 1)
            {
                int v, x;
                cin >> v >> x;
                arr[v] = x;
                update(1, 1, n, start[v], arr[v]);
            }
            else
            {
                int v;
                cin >> v;
                int s = start[v], e = end[v];
                vector<int> basis = query(1, 1, n, s, e);
                int cnt = 0;
                for(i=0;i<20;i++)
                    if(basis[i])
                        cnt++;
                cout << (mypower(2, e - s + 1 - cnt) + mod - 1)%mod << 'n';
            }
        }
    }
    return 0;
}

HackerEarth Tree queries problem solution.

Leave a Reply