Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Knapsack DP is harder than FFT.
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 3e5 + 225, L = 19;
- int n, m, q;
- vector<int> adj[N], bct[N * 2];
- int pre[N], low[N], cnt;
- int stk[N], top, bcc;
- void tarjan(int u){
- pre[u] = low[u] = ++cnt;
- stk[++top] = u;
- for(int v: adj[u]){
- if(!pre[v]){
- tarjan(v);
- chmin(low[u], low[v]);
- if(low[v] == pre[u]){
- ++bcc;
- for(int z = 0; z != v; --top){
- z = stk[top];
- bct[z].pb(bcc + n);
- bct[bcc + n].pb(z);
- }
- bct[u].pb(bcc + n);
- bct[bcc + n].pb(u);
- }
- } else chmin(low[u], pre[v]);
- }
- }
- int dep[N * 2], anc[L + 1][N * 2];
- void dfs(int u, int d){
- dep[u] = d;
- for(int v: bct[u])
- if(!dep[v]){
- dfs(v, d + 1);
- anc[0][v] = u;
- }
- }
- void initLCA(){
- for(int l = 1; l < L + 1; ++l)
- for(int i = 1; i <= bcc + n; ++i)
- anc[l][i] = anc[l-1][anc[l-1][i]];
- }
- void jump(int &a, int d){
- for(int i = L; i >= 0; --i)
- if(d >> i & 1) a = anc[i][a];
- }
- int LCA(int a, int b){
- if(dep[a] < dep[b]) swap(a, b);
- jump(a, dep[a] - dep[b]);
- if(a == b) return a;
- for(int i = L; i >= 0; --i)
- if(anc[i][a] != anc[i][b]){
- a = anc[i][a];
- b = anc[i][b];
- }
- return anc[0][a];
- }
- void solve(){
- // Get BCC &
- // Make Circle Square Tree
- tarjan(1), --top;
- // Do LCA Stufz
- dfs(1, 1);
- initLCA();
- }
- bool query(int a, int b, int c){
- int lca = LCA(b, c);
- if(lca > n and dep[a] < dep[lca] - 1) return false;
- if(lca <= n and dep[a] < dep[lca]) return false;
- if(lca > n and a == anc[0][lca]) return true;
- if(lca <= n and a == lca) return true;
- if(dep[b] >= dep[a]){
- jump(b, dep[b] - dep[a]);
- if(b == a) return true;
- }
- if(dep[c] >= dep[a]){
- jump(c, dep[c] - dep[a]);
- if(c == a) return true;
- }
- return false;
- }
- int main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- cin >> n >> m >> q;
- for(int u, v; m; --m){
- cin >> u >> v;
- adj[u].pb(v);
- adj[v].pb(u);
- }
- solve();
- for(int a, b, c; q; --q){
- cin >> a >> b >> c;
- bool ans = query(a, b, c) or query(b, a, c) or query(c, a, b);
- cout << (ans ? "Yes\n" : "No\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement