HackerEarth Two paths problem solution YASH PAL, 31 July 2024 In this HackerEarth Two paths problem solution Given an undirected graph with n vertices and m edges. Each edge is one of the two types: white and black. There are q queries denoted by four vertices a, b, c and d. Each query asks: can some of the black edges be deleted, so that a is reachable from b, but c is not reachable from d? Note that graph itself doesn’t change from query to query. HackerEarth Two paths problem solution. #include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <cmath>#include <ctime>#include <functional>#include <sstream>#include <fstream>#include <valarray>#include <complex>#include <queue>#include <cassert>#include <bitset>using namespace std;#ifdef LOCAL#define debug_flag 0#else#define debug_flag 0#endif template <class T1, class T2 >std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) { os << "[" << p.first << ", " << p.second << "]"; return os;} template <class T >std::ostream& operator << (std::ostream& os, const std::vector<T>& v) { os << "["; bool first = true; for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) { if (!first) os << ", "; first = false; os << *it; } os << "]"; return os;}#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }vector<string> _split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.emplace_back(x); return v;}void _print(vector<string>::iterator) {}template<typename T, typename... Args>void _print(vector<string>::iterator it, T a, Args... args) { string name = it -> substr((*it)[0] == ' ', it -> length()); if (isalpha(name[0])) cerr << name << " = " << a << " "; else cerr << name << " "; _print(++it, args...);}typedef long long int int64;const int N = (int)4e5 + 1000;const int LOGN = 20;int n, m, q;vector<int> graph[N];vector<pair<int, int> > black_edges;int white_comp_cnt;int v_to_white_comp[N];int timer;int t_in[N], t_out[N];int f_up[N];bool is_articulation_point[N];int block_cnt;int block_id[N];vector<int> cur_block;vector<int> block_graph[N];int par[N][LOGN];bool used[N];int black_color[N];vector<vector<int> > blocks;void dfs_comp(int v){ v_to_white_comp[v] = white_comp_cnt; for (int to : graph[v]) if (v_to_white_comp[to] == -1) dfs_comp(to);}void proccess_block(int limit_size){ vector<int> cur_comp; while ((int)cur_block.size() > limit_size) { cur_comp.push_back(cur_block.back()); cur_block.pop_back(); } blocks.push_back(cur_comp);}void init_dfs(int v, int p, int cur_black_color){ //dbg(v, p); black_color[v] = cur_black_color; cur_block.push_back(v); t_in[v] = f_up[v] = timer++; used[v] = true; int to_cnt = 0; for (int to : graph[v]) { if (to == p) continue; if (used[to]) { f_up[v] = min(f_up[v], t_in[to]); } else { int limit_size = (int)cur_block.size(); to_cnt++; init_dfs(to, v, cur_black_color); if (f_up[to] >= t_in[v]) { if (p != -1 || (p == -1 && to_cnt > 1)) { proccess_block(limit_size); blocks.back().push_back(v); } if (p != -1) is_articulation_point[v] = true; } f_up[v] = min(f_up[v], f_up[to]); } } if (p == -1) is_articulation_point[v] = (to_cnt > 1);}bool is_par(int p, int v){ return t_in[p] <= t_in[v] && t_out[v] <= t_out[p];}int get_lca(int a, int b){ if (is_par(a, b)) return a; if (is_par(b, a)) return b; for (int i = LOGN - 1; i >= 0; i--) { int new_a = par[a][i]; if (new_a == -1 || is_par(new_a, b)) continue; a = new_a; } return par[a][0];}void block_dfs(int v, int p){ t_in[v] = timer++; used[v] = true; par[v][0] = p; for (int i = 1; i < LOGN; i++) { if (par[v][i - 1] == -1) break; par[v][i] = par[par[v][i - 1]][i - 1]; } for (int to : block_graph[v]) { if (used[to]) continue; block_dfs(to, v); } t_out[v] = timer++;}void init_graph(){ fill(v_to_white_comp, v_to_white_comp + n, -1); for (int i = 0; i < n; i++) { if (v_to_white_comp[i] != -1) continue; dfs_comp(i); white_comp_cnt++; } //for (int i = 0; i < n; i++) //dbg(i, v_to_white_comp[i]); for (int i = 0; i < n; i++) graph[i].clear(); for (auto p : black_edges) { int a = p.first; int b = p.second; a = v_to_white_comp[a]; b = v_to_white_comp[b]; if (a != b) { //dbg("black", a, b); graph[a].push_back(b); graph[b].push_back(a); } } fill(used, used + white_comp_cnt, false); int black_cnt = 0; fill(block_id, block_id + n, -1); for (int i = 0; i < white_comp_cnt; i++) { if (used[i]) continue; init_dfs(i, -1, black_cnt); black_cnt++; proccess_block(0); } dbg(blocks); for (int i = 0; i < white_comp_cnt; i++) dbg(i, is_articulation_point[i]); block_cnt = (int)blocks.size() + white_comp_cnt; dbg(block_cnt); for (int i = 0; i < (int)blocks.size(); i++) { for (int v : blocks[i]) { block_id[v] = i; if (is_articulation_point[v]) { int a = i; int b = v + (int)blocks.size(); dbg("block edge", a, b); block_graph[a].push_back(b); block_graph[b].push_back(a); } } } fill(used, used + block_cnt, false); for (int i = 0; i < block_cnt; i++) for (int j = 0; j < LOGN; j++) par[i][j] = -1; for (int i = 0; i < block_cnt; i++) { if (used[i]) continue; block_dfs(i, -1); } //for (int i = 0; i < white_comp_cnt; i++) //dbg(i, is_articulation_point[i]);}bool on_path(int v, int a, int b){ return is_par(b, v) && is_par(v, a);}bool check(int a, int b, int c){ dbg("check", a, b, c); //a != b holds if (c == a || c == b) return false; if (!is_articulation_point[c]) return true; if (is_articulation_point[a]) a = (int)blocks.size() + a; else a = block_id[a]; if (is_articulation_point[b]) b = (int)blocks.size() + b; else b = block_id[b]; c = (int)blocks.size() + c; int lca = get_lca(a, b); dbg(a, b, c, lca); if (on_path(c, a, lca) || on_path(c, b, lca)) return false; return true;}bool solve(int a, int b, int c, int d){ a = v_to_white_comp[a]; b = v_to_white_comp[b]; c = v_to_white_comp[c]; d = v_to_white_comp[d]; //dbg(a, b, c, d); if (black_color[a] != black_color[b]) return false; if (black_color[c] != black_color[d]) return true; if (c == d) return false; if (a == b) return true; if (check(a, b, c)) return true; if (check(a, b, d)) return true; return false;}int main(){#ifdef LOCAL freopen ("input.txt", "r", stdin);#endif scanf("%d%d%d", &n, &m, &q); for (int i = 0; i < m; i++) { int a, b, t; scanf("%d%d%d", &a, &b, &t); a--; b--; dbg(a, b, t); if (t == 0) black_edges.emplace_back(a, b); else { graph[a].push_back(b); graph[b].push_back(a); } } init_graph(); for (int i = 0; i < q; i++) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); a--; b--; c--; d--; dbg(a, b, c, d); bool res = solve(a, b, c, d); printf("%sn", res ? "Yes" : "No"); } return 0;} coding problems