Advertisement
FHVirus

Untitled

Feb 4th, 2021 (edited)
292
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. //Knapsack DP is harder than FFT.
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int N = 3e5 + 225, L = 19;
  6. int n, m, q;
  7. vector<int> adj[N], bct[N * 2];
  8. int pre[N], low[N], cnt;
  9. int stk[N], top, bcc;
  10.  
  11. void tarjan(int u){
  12.     pre[u] = low[u] = ++cnt;
  13.     stk[++top] = u;
  14.     for(int v: adj[u]){
  15.         if(!pre[v]){
  16.             tarjan(v);
  17.             chmin(low[u], low[v]);
  18.             if(low[v] == pre[u]){
  19.                 ++bcc;
  20.                 for(int z = 0; z != v; --top){
  21.                     z = stk[top];
  22.                     bct[z].pb(bcc + n);
  23.                     bct[bcc + n].pb(z);
  24.                 }
  25.                 bct[u].pb(bcc + n);
  26.                 bct[bcc + n].pb(u);
  27.             }
  28.         } else chmin(low[u], pre[v]);
  29.     }
  30. }
  31.  
  32. int dep[N * 2], anc[L + 1][N * 2];
  33. void dfs(int u, int d){
  34.     dep[u] = d;
  35.     for(int v: bct[u])
  36.         if(!dep[v]){
  37.             dfs(v, d + 1);
  38.             anc[0][v] = u;
  39.         }
  40. }
  41. void initLCA(){
  42.     for(int l = 1; l < L + 1; ++l)
  43.         for(int i = 1; i <= bcc + n; ++i)
  44.             anc[l][i] = anc[l-1][anc[l-1][i]];
  45. }
  46. void jump(int &a, int d){
  47.     for(int i = L; i >= 0; --i)
  48.         if(d >> i & 1) a = anc[i][a];
  49. }
  50. int LCA(int a, int b){
  51.     if(dep[a] < dep[b]) swap(a, b);
  52.     jump(a, dep[a] - dep[b]);
  53.     if(a == b) return a;
  54.     for(int i = L; i >= 0; --i)
  55.         if(anc[i][a] != anc[i][b]){
  56.             a = anc[i][a];
  57.             b = anc[i][b];
  58.         }
  59.     return anc[0][a];
  60. }
  61.  
  62. void solve(){
  63.     // Get BCC &
  64.     // Make Circle Square Tree
  65.     tarjan(1), --top;
  66.     // Do LCA Stufz
  67.     dfs(1, 1);
  68.     initLCA();
  69. }
  70.  
  71. bool query(int a, int b, int c){
  72.     int lca = LCA(b, c);
  73.     if(lca > n and dep[a] < dep[lca] - 1) return false;
  74.     if(lca <= n and dep[a] < dep[lca]) return false;
  75.     if(lca > n and a == anc[0][lca]) return true;
  76.     if(lca <= n and a == lca) return true;
  77.    
  78.     if(dep[b] >= dep[a]){
  79.         jump(b, dep[b] - dep[a]);
  80.         if(b == a) return true;
  81.     }
  82.     if(dep[c] >= dep[a]){
  83.         jump(c, dep[c] - dep[a]);
  84.         if(c == a) return true;
  85.     }
  86.     return false;
  87. }
  88.  
  89. int main(){
  90.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  91.     cin >> n >> m >> q;
  92.     for(int u, v; m; --m){
  93.         cin >> u >> v;
  94.         adj[u].pb(v);
  95.         adj[v].pb(u);
  96.     }
  97.     solve();
  98.     for(int a, b, c; q; --q){
  99.         cin >> a >> b >> c;
  100.         bool ans = query(a, b, c) or query(b, a, c) or query(c, a, b);
  101.         cout << (ans ? "Yes\n" : "No\n");
  102.     }
  103.     return 0;
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement