[Hackerearth] Leafonomics

Problem Link    : Leafonomics 
Category        : DP on Tree
Contest         : January Circuits '24 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int INF = 1e18;
 
struct Node {
    int v, w;
    Node(int v = 0, int w = 0)
        : v(v), w(w) {}
};
 
int n;
vector<vector<Node>> graph;
vector<int> in;
 
void dfs(int u, int p) {
    int &mini = in[u];
    mini = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        dfs(v, u);
        mini = min(mini, w + in[v]);
    }
    if (mini == INF) {
        mini = 0;
    }
}
 
vector<int> out;
 
void solve(int u, int p) {
    int firstMin = INF;
    int secondMin = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int cur = w + in[v];
        if (cur < firstMin) {
            secondMin = firstMin;
            firstMin = cur;
        } else if (cur < secondMin) {
            secondMin = cur;
        }
    }
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int use = w + in[v] == firstMin ? secondMin : firstMin;
        out[v] = min(w + out[u], w + use);
        solve(v, u);
    }
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    in.clear(); in.resize(n + 1);
    dfs(1, 0);
    out.clear(); out.resize(n + 1, INF);
    solve(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << min(in[i], out[i]) << " \n"[i == n];
    }
}
 
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] 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] Odd Bit Array

 

Problem Link    : Odd Bit Array
Category        : Xor, DP, DP Optimization
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
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++) {
        int n;
        cin >> n;
        vector<int> arr(n);
        vector<int> parity(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            parity[i] = __builtin_popcount(arr[i]) & 1;
        }
        vector<int> paritysum(n);
        for (int i = n - 1; i >= 0; i--) {
            paritysum[i] = parity[i] + (i + 1 < n ? paritysum[i + 1] : 0);
        }
        vector<mint> dp(n);
        vector<mint> results(2);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int lookup = paritysum[i] & 1;
            if (parity[i] == 0) {
                lookup ^= 1;
            }
            cnt += parity[i];
            dp[i] = results[lookup];
            if (cnt & 1) {
                dp[i] += 1;
            }
            if (i + 1 < n) {
                results[ paritysum[i + 1] & 1 ] += dp[i];
            }
        }
        cout << dp.back() << endl;
    }
 
}