fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl '\n'
  6. #define fu(i,a,b) for(int i=a; i<=b; i++)
  7. #define fd(i,a,b) for(int i=a; i>=b; i--)
  8. #define BIT(i, n) (((n) >> (i)) & 1)
  9. #define SZ(s) ((int)(s.size()))
  10. #define pb push_back
  11. #define eb emplace_back
  12. #define pii pair<int, int>
  13. #define all(v) v.begin(), v.end()
  14. #define ff first
  15. #define ss second
  16. #define ins insert
  17.  
  18. int t,n,m,q,k;
  19.  
  20. const int N = 1e5+5;
  21. const int MOD = 1e9+7;
  22. const int inf = 1e9+7;
  23. const int base = 311;
  24. const int nr = 505;
  25. void add(int &a, int b){a+=b; if(a>=MOD) a-=MOD;}
  26. void sub(int &a, int b){a-=b; if(a<0) a+=MOD;}
  27.  
  28. pii edges[5*N];
  29. vector<pii> adj[N];
  30. vector<int> dsk[N];
  31. int par[N][18], h[N], low[N], num[N], scc[N];
  32. int timedfs, cnt;
  33. stack<int> st;
  34.  
  35.  
  36. void dfs(int u, int id){
  37.     num[u] = low[u] = ++timedfs;
  38.     st.push(u);
  39.     for(pii it: adj[u]){
  40.         if(it.ss == id) continue;
  41.         if(!num[it.ff]){
  42.             dfs(it.ff, it.ss);
  43.             low[u] = min(low[u], low[it.ff]);
  44.         }else low[u] = min(low[u], num[it.ff]);
  45.     }
  46.     if(num[u] == low[u]){
  47.         int v=-1;
  48.         ++cnt;
  49.         while(v!=u){
  50.             v = st.top();
  51.             st.pop();
  52.             scc[v] = cnt;
  53.             low[v] = num[v] = inf;
  54.         }
  55.     }
  56. }
  57.  
  58. void dfs_tree(int u, int p){
  59.     for(int v: dsk[u]){
  60.         if(v==p) continue;
  61.         h[v] = h[u]+1;
  62.         par[v][0] = u;
  63.         for(int i=1; (1<<i) <= h[v]; i++)
  64.             par[v][i] = par[par[v][i-1]][i-1];
  65.         dfs_tree(v, u);
  66.     }
  67. }
  68.  
  69. int LCA(int u, int v){
  70.     if(h[u]<h[v]) swap(u,v);
  71.     int dis=h[u]-h[v];
  72.     for(int i=0; (1<<i)<=dis; i++)
  73.         if(BIT(i, dis)) 
  74.             u=par[u][i];
  75.     if(u==v) return u;
  76.     int lg=__lg(h[u]);
  77.     fd(i,lg,0)
  78.         if(par[u][i]!=par[v][i])
  79.             u=par[u][i], v=par[v][i];
  80.     return par[u][0];
  81. }
  82.  
  83. void build_tree(){
  84.     fu(i,1,m) 
  85.         if(scc[edges[i].ff] != scc[edges[i].ss]){
  86.             dsk[scc[edges[i].ff]].eb(scc[edges[i].ss]);
  87.             dsk[scc[edges[i].ss]].eb(scc[edges[i].ff]);
  88.         }
  89. }
  90.  
  91. int calc(int u, int v){
  92.     return h[u] + h[v] - 2*h[LCA(u,v)];
  93. }
  94.  
  95. void nhap(){
  96.     cin >> n >> m >> q;
  97.     fu(i,1,m){
  98.         int u,v;
  99.         cin >> u >> v;
  100.         edges[i] = {u, v};
  101.         if(u==v) continue;
  102.         adj[u].eb(v, i);
  103.         adj[v].eb(u, i);
  104.     }
  105.     dfs(1,0);
  106.     build_tree();
  107.     dfs_tree(1,0);
  108.     while(q--){
  109.         int u,v,w;
  110.         cin >> u >> v >> w;
  111.         u = scc[u];
  112.         v = scc[v];
  113.         w = scc[w];
  114.         int x = ((LCA(u,v)^LCA(u,w))^(LCA(v,w)));
  115.         cout << calc(x,u) + calc(x,v) + calc(x,w) << nl;
  116.     }
  117. }
  118.  
  119. int main(){
  120.     ios_base::sync_with_stdio(0);
  121.     cin.tie(0); cout.tie(0);
  122.     if(fopen("quan.inp", "r")){
  123.         freopen("quan.inp", "r", stdin);
  124.         freopen("quan.out", "w", stdout);
  125.     }
  126.     nhap();
  127. }
  128.  
Success #stdin #stdout 0.01s 13908KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UvnWxQ
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!