[Toph] D. Mushroom Kingdom

 

Problem Link    : D. Mushroom Kingdom
Category        : Bitmask, Bfs
Contest         : Intra AIUB Programming Contest 2024 (Senior)

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
int dr[] = {1, -1, 0, 0}; // 4 Direction
int dc[] = {0, 0, 1, -1};
 
void task() {
    int n;
    cin >> n;
    vector<char> chars;
    vector<vector<char>> grid(n + 1, vector<char>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
            chars.push_back(grid[i][j]);
        }
    }
    pii src;
    cin >> src.first >> src.second;
    pii des;
    cin >> des.first >> des.second;
    sort(chars.begin(), chars.end());
    chars.erase(unique(chars.begin(), chars.end()), chars.end());
    int ans = 10;
    for (int mask = 0; mask < (1 << (int)chars.size()); mask++) {
        set<int> validChars;
        for (int i = 0; i < chars.size(); i++) {
            if (mask >> i & 1) {
                validChars.insert(chars[i]);
            }
        }
        vector<vector<bool>> visited(n + 1, vector<bool>(n + 1));
        queue<pii> pq;
        if (validChars.count(grid[src.first][src.second])) {
            pq.push(src);
            visited[src.first][src.second] = 1;
        }
        while (pq.size()) {
            pii cur = pq.front(); pq.pop();
            for (int k = 0; k < 4; k++) {
                int x = cur.first + dr[k];
                int y = cur.second + dc[k];
                if (x >= 1 and x <= n and y >= 1 and y <= n and visited[x][y] == 0 and validChars.count(grid[x][y])) {
                    pq.push(pii(x, y));
                    visited[x][y] = 1;
                }
            }
        }
        if (visited[des.first][des.second]) {
            ans = min(ans, (int)__builtin_popcount(mask));
        }
    }
    cout << ans << 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++) {
        task();
    }
}
 

[Toph] B. Dictionary Tree

 

Problem Link    : B. Dictionary Tree
Category        : Trie, Tree, Dfs
Contest         : Intra AIUB Programming Contest 2024 (Senior)

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
struct Trie {
    int counter;
    Trie *child[26];
    Trie *parent;
 
    Trie() {
        counter = 0;
        parent = nullptr;
        for (int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (child[i] and this != child[i]) {
                delete child[i];
            }
        }
    }
};
 
typedef Trie* pnode;
pnode root;
 
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 n, k;
    cin >> n >> k;
    vector<vector<int>> graph(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);
    }
    vector<char> letters(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> letters[i];
    }
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end(), [&](int x, int y)
            {
               return letters[x] < letters[y];
            });
    }
    root = new Trie();
    pnode curRoot = root;
    function<void(int, int)> Dfs = [&](int u, int p) {
        if (curRoot->child[ letters[u] - 'a' ] == nullptr) {
            curRoot->child[ letters[u] - 'a' ] = new Trie();
            curRoot->child[ letters[u] - 'a' ]->parent = curRoot;
            curRoot = curRoot->child[ letters[u] - 'a' ];
            curRoot->counter++;
        } else {
            curRoot->child[ letters[u] - 'a' ]->parent = curRoot;
            curRoot = curRoot->child[ letters[u] - 'a' ];
            curRoot->counter++;
        }
        for (int v : graph[u]) {
            if (v == p) {
                continue;
            }
            Dfs(v, u);
        }
        curRoot = curRoot->parent;
    };
    Dfs(1, 0);
    string path = "";
    function<void(pnode)> Solve = [&](pnode rt) {
        if (rt == nullptr) {
            return;
        }
        if (k <= 0) {
            cout << path << endl;
            exit(0);
        }
        for (int i = 0; i < 26; i++) {
            if (rt->child[i] == nullptr) {
                continue;
            }
            path += static_cast<char>(i + 'a');
            k -= rt->child[i]->counter;
            Solve(rt->child[i]);
            path.pop_back();
        }
    };
    Solve(root);
}

[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();
    }
}