Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define endl "\n"
- #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- using namespace std;
- const int N = 3e5 + 10;
- pair<int, int> gmin(int a, int b) {
- return {min(a, b), max(a, b)};
- }
- //graph itself
- int n, m, q, timer;
- vector<int> gr[N], g[N];
- //vis
- vector<int> vis;
- struct dsu {
- vector<int> par, siz;
- int get(int v) {
- if(par[v] == v) return v;
- return par[v] = get(par[v]);
- }
- void uni(int a, int b) {
- a = get(a);
- b = get(b);
- if(a != b) {
- if(siz[a] > siz[b]) {
- swap(a, b);
- }
- par[a] = b;
- siz[b] += siz[a];
- }
- }
- void resize(int n) {
- par.resize(n + 1);
- siz.resize(n + 1);
- for(int i = 1; i <= n; i++) {
- par[i] = i;
- siz[i] = 1;
- }
- }
- } comp, strong;
- //find bridges
- vector<pair<int, int>> bridges;
- vector<int> fup(N), tin(N);
- int up[N][20], tout[N], art[N];
- void bdfs(int v, int pr = -1) {
- fup[v] = tin[v] = timer++;
- vis[v] = 1;
- int cnt = 0;
- for(auto it: gr[v]) {
- if(it == pr) continue;
- if(!vis[it]) {
- bdfs(it, v);
- fup[v] = min(fup[it], fup[v]);
- cnt++;
- } else {
- fup[v] = min(fup[v], tin[it]);
- }
- comp.uni(v, it);
- if(fup[it] > tin[v]) {
- bridges.push_back(gmin(it, v));
- }
- if(fup[it] >= tin[v] && pr != -1) {
- art[v] = 1;
- }
- }
- if(cnt > 1 && pr == -1) {
- art[v] = 1;
- }
- tout[v] = timer;
- }
- void sbfs(int v) {
- vis[v] = 1;
- for(auto it: gr[v]) {
- if(binary_search(bridges.begin(), bridges.end(), gmin(v, it)) || vis[it]) continue;
- strong.uni(v, it);
- sbfs(it);
- }
- }
- void calc(int v, int pr) {
- vis[v] = 1;
- up[v][0] = pr;
- for(int i = 1; i < 20; i++) {
- up[v][i] = up[up[v][i - 1]][i - 1];
- }
- for(auto it: g[v]) {
- if(it == pr) continue;
- calc(it, v);
- }
- }
- bool upper(int a, int b) {
- return tin[a] <= tin[b] && tout[a] >= tout[b];
- }
- int lca(int a, int b) {
- if(upper(a, b)) return a;
- if(upper(b, a)) return b;
- for(int i = 19; i >= 0; i--) {
- if(!upper(up[a][i], b)) {
- a = up[a][i];
- }
- }
- return up[a][0];
- }
- main() {
- boost;
- cin >> n >> m >> q;
- comp.resize(n);
- strong.resize(n);
- vis.resize(n + 1);
- while(m--) {
- int l, r;
- cin >> l >> r;
- gr[l].push_back(r);
- gr[r].push_back(l);
- }
- for(int i = 1; i <= n; i++) {
- if(!vis[i]) {
- bdfs(i);
- }
- }
- sort(bridges.begin(), bridges.end());
- fill(vis.begin(), vis.end(), 0);
- //split into comps
- for(int i = 1; i <= n; i++) {
- if(!vis[i]) {
- sbfs(i);
- }
- }
- //build new tree
- for(auto it: bridges) {
- int l = it.first, r = it.second;
- l = strong.get(l);
- r = strong.get(r);
- g[l].push_back(r);
- g[r].push_back(l);
- }
- fill(vis.begin(), vis.end(), 0);
- //lca shit goes here ...
- timer = 0;
- for(int i = 1; i <= n; i++) {
- if(!vis[strong.get(i)]) {
- calc(strong.get(i), strong.get(i));
- }
- }
- //end lca shit
- //go for queries
- while(q--) {
- int a, b, c;
- cin >> a >> b >> c;
- int sa, sb, sc;
- if(a == b && b != c) {
- cout << "NO" << endl;
- continue;
- }
- sa = strong.get(a), sb = strong.get(b), sc = strong.get(c);
- if(comp.get(a) != comp.get(b) || comp.get(a) != comp.get(c) || comp.get(b) != comp.get(c)) {
- cout << "NO" << endl;
- continue;
- }
- // i just made sure that all a b c are in same comp
- if(sa == sb && sb == sc) {
- cout << "YES" << endl;
- continue;
- }
- //all in one cycle -
- if(a == c || b == c) {
- cout << "YES" << endl;
- continue;
- }
- if(tin[a] > tin[b]) {
- swap(sa, sb);
- swap(a, b);
- }
- if(binary_search(bridges.begin(), bridges.end(), gmin(a, b))) {
- cout << "NO" << endl;
- continue;
- }
- //a and c in same strong
- if(sa == sc) {
- if(art[a]) {
- //deep analysis
- } else {
- cout << "YES" << endl;
- }
- continue;
- }
- if(sb == sc) {
- if(art[b]) {
- cout << "NO" << endl;
- } else {
- cout << "YES" << endl;
- }
- continue;
- }
- //bad code here
- if(sb == sa) {
- if(art[b]) {
- cout << "NO" << endl;
- } else {
- cout << "YES" << endl;
- }
- continue;
- }
- //last part, is c on simple path in the tree
- //a = c -> b
- if(upper(sa, sb)) {
- if(upper(sc, sb) && upper(sa, sc)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- continue;
- }
- int mid = lca(sa, sb);
- if(upper(mid, c) && (upper(c, b) || upper(c, a))) {
- cout << "YES" << endl;
- continue;
- }
- cout << "NO" << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement