[Hackerearth] RebelReach

 

Problem Link    : RebelReach
Category        : Graph, Binary Search
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
int n;
int q;
vector<vector<int>> graph;
vector<int> guards;
vector<vector<pii>> queries;
vector<int> arr;
vector<int> cumsum;
vector<int> ans;
 
void dfs(int u, int p) {
    arr.push_back(u);
    cumsum.push_back(guards[u] + (cumsum.size() ? cumsum.back() : 0));
    for (pii it : queries[u]) {
        int x = it.first;
        int lo = 0;
        int hi = arr.size() - 1;
        int id = arr.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            int sum = cumsum.back() - (mid - 1 >= 0 ? cumsum[mid - 1] : 0);
            if (sum <= x) {
                id = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        int sum = cumsum.back() - (id - 1 >= 0 ? cumsum[id - 1] : 0);
        ans[it.second] = arr[id];
        if (sum < x and id - 1 >= 0) {
            ans[it.second] = arr[id - 1];
        }
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    arr.pop_back();
    cumsum.pop_back();
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    guards.clear(); guards.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> guards[i];
    }
    cin >> q;
    queries.clear(); queries.resize(n + 1);
    for (int i = 0; i < q; i++) {
        int u, x;
        cin >> u >> x;
        queries[u].push_back(pii(x, i));
    }
    arr.clear();
    cumsum.clear();
    ans.clear(); ans.resize(q);
    dfs(1, 0);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}

[Hackerearth] Xorzilla

 

Problem Link    : Xorzilla
Category        : Graph Theory, Bit
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 2e5 + 5;
const int logn = 20;
 
int n;
vector<int> arr;
vector<vector<int>> graph;
vector<int> depth;
vector<vector<int>> father;
vector<int> cumxor;
 
void dfs(int u, int p, int lvl) {
    depth[u] = lvl;
    cumxor[u] = arr[u] ^ cumxor[p];
    for (int i = 1; i < logn; i++) {
        father[u][i] = father[ father[u][i - 1] ][i - 1];
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        father[v][0] = u;
        dfs(v, u, lvl + 1);
    }
}
 
int findLca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (depth[ father[u][i] ] >= depth[v]) {
            u = father[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (father[u][i] != father[v][i]) {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
int getMax(int u, int v, int x) {
    int lca = findLca(u, v);
    int xorsum = cumxor[u] ^ cumxor[v] ^ arr[lca];
    int dist = depth[u] + depth[v] - 2 * depth[lca];
    if (dist % 2) {
        return xorsum;
    }
    int maxi = 0;
    for (int i = 30; i >= 0; i--) {
        bool bit = xorsum >> i & 1LL;
        if (bit == 0) {
            if (maxi + (1LL << i) <= x) {
                maxi = maxi + (1LL << i);
            }
        }
    }
    return xorsum ^ maxi;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        cin >> n;
        arr.clear(); arr.resize(n + 1);
        depth.clear(); depth.resize(n + 1);
        graph.clear(); graph.resize(n + 1);
        cumxor.clear(); cumxor.resize(n + 1);
        father = vector<vector<int>>(n + 1, vector<int>(logn));
        for (int e = 1; e < n; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        dfs(1, 0, 1);
        int q;
        cin >> q;
        while (q--) {
            int x, u, v;
            cin >> x >> u >> v;
            cout << getMax(u, v, x) << endl;
        }
    }
}

[Hackerearth] Cryptic Line

 

Problem Link    : Cryptic Line
Category        : Graph Theory
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
int n;
int q;
vector<vector<int>> graph;
vector<int> in;
vector<int> out;
int dfsTime;
 
void dfs(int u, int p) {
    in[u] = ++dfsTime;
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    out[u] = dfsTime;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    cin >> n >> q;
    graph.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (in[x] < in[y] and out[x] >= out[y]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

[CS Academy] Root Change

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Root Change
Source            : CS Academy 
Category          : Graph Theory, Tree
Algorithm         : Re-Rooting Technique
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int   
#define endl         '\n'  
  
static const int maxn = 2e5 + 5;  
static const int logn = 19;  
  
vector < vector <int> > graph;  
int depth[maxn];  
int father[maxn][logn];  
  
void dfs(int u, int p = -1) {  
    for (int i = 1; i < logn; i++) {  
        father[u][i] = father[ father[u][i - 1] ][i - 1];  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        depth[v] = depth[u] + 1;  
        father[v][0] = u;  
        dfs(v, u);  
    }  
}  
  
int find_lca(int u, int v) {  
    if (depth[u] < depth[v]) {  
        swap(u, v);  
    }  
    for (int i = logn - 1; i >= 0; i--) {  
        if (depth[ father[u][i] ] >= depth[v]) {  
            u = father[u][i];  
        }  
    }  
    if (u == v) {  
        return u;  
    }  
    for (int i = logn - 1; i >= 0; i--) {  
        if (father[u][i] != father[v][i]) {  
            u = father[u][i];  
            v = father[v][i];  
        }  
    }  
    return father[u][0];  
}  
  
int dist(int u, int v) {  
    int lca = find_lca(u, v);  
    return depth[u] + depth[v] - 2 * depth[lca];  
}  
  
#define pii           pair <int, int>  
#define mk            make_pair  
#define ff            first  
#define ss            second  
  
pii dp[maxn];  
  
void solve(int u, int p = -1) {  
    dp[u] = mk(0, u);  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        solve(v, u);  
        if (1 + dp[v].ff > dp[u].ff) {  
            dp[u].ff = 1 + dp[v].ff;  
            dp[u].ss = dp[v].ss;  
        }  
    }  
    int cnt = 0;  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        if (1 + dp[v].ff == dp[u].ff) {  
            cnt++;  
        }  
    }  
    if (cnt > 1) {  
        dp[u].ss = u;  
    }  
}  
  
int n;  
int ans[maxn];  
pii dp2[maxn];  
  
void solution(int u, int p = 0) {  
    ans[u] = n - 1 - dist(u, dp[u].ss);  
    set <pii> st;  
    int maxi = 0;  
    if (p) {  
        maxi = dp[p].ff;  
        st.insert(dp[p]);  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        if (dp[v].ff > maxi) {  
            maxi = dp[v].ff;  
        }   
        st.insert(dp[v]);  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        pii tempu = dp[u];  
        pii tempv = dp[v];  
        st.erase(dp[v]);  
        if (st.size() == 0) {  
            dp[u].ff = 0;  
            dp[u].ss = u;  
        } else {  
            pii beg = *st.rbegin();  
            dp[u].ff = 1 + beg.ff;  
            dp[u].ss = beg.ss;  
            st.erase(beg);  
            if (st.size()) {  
                pii chk = *st.rbegin();  
                if (chk.ff == beg.ff) {  
                    dp[u].ss = u;  
                }  
            }  
            st.insert(beg);  
        }  
        if (1 + dp[u].ff > dp[v].ff) {  
            dp[v].ff = 1 + dp[u].ff;  
            dp[v].ss = dp[u].ss;  
        } else if (1 + dp[u].ff == dp[v].ff) {  
            dp[v].ss = v;  
        }  
        st.insert(tempv);  
        solution(v, u);  
        dp[u] = tempu;  
        dp[v] = tempv;  
    }  
}  
  
signed main()  
{  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
      
    cin >> n;  
    graph.resize(n + 1);  
    for (int e = 1; e < n; e++) {  
        int u, v;  
        cin >> u >> v;  
        graph[u].push_back(v);  
        graph[v].push_back(u);  
    }  
    int root = 1;  
    for (int i = 1; i <= n; i++) {  
        if (graph[i].size() == 1) {  
            root = i;  
            break;  
        }   
    }  
    depth[root] = 1;  
    dfs(root);  
    solve(root);  
    solution(root);  
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;  
}