fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16. #define LOG 20
  17.  
  18. const ll MAX=1e5+5;
  19. int n,m,q;
  20. vector<pair<int,int> > adj[MAX];
  21.  
  22. int compCount,compID[MAX];
  23. stack<int> st;
  24. int timer=0,low[MAX],num[MAX];
  25. void dfs(int u, int id)
  26. {
  27.     num[u]=low[u]=++timer;
  28.     st.push(u);
  29.     for(pair<int,int> pa:adj[u])
  30.     {
  31.         int v=pa.fi, idx=pa.se;
  32.         if(idx==id) continue;
  33.         if(num[v]) low[u]=min(low[u],num[v]);
  34.         else
  35.         {
  36.             dfs(v,idx);
  37.             low[u]=min(low[u],low[v]);
  38.             if(low[v]>num[u])
  39.             {
  40.                 ++compCount;
  41.                 while(true)
  42.                 {
  43.                     int t=st.top(); st.pop();
  44.                     compID[t]=compCount;
  45.                     if(t==v) break;
  46.                 }
  47.             }
  48.         }
  49.     }
  50. }
  51. vector<pair<int,int> > adjTree[MAX];
  52. int logn,h[MAX],jump[LOG][MAX],dist[LOG][MAX];
  53. void dfs1(int u, int p)
  54. {
  55.     for(pair<int,int> pa:adjTree[u])
  56.     {
  57.         int v=pa.fi, w=pa.se;
  58.         if(v==p) continue;
  59.         h[v]=h[u]+1;
  60.         jump[0][v]=u;
  61.         dist[0][v]=w;
  62.         dfs1(v,u);
  63.     }
  64. }
  65.  
  66. void buildLCA()
  67. {
  68.     dfs1(1,0);
  69.     logn=31-__builtin_clz(compCount);
  70.     foru(j,1,logn)
  71.     {
  72.         foru(i,1,compCount)
  73.         {
  74.             int t=jump[j-1][i];
  75.             jump[j][i]=jump[j-1][t];
  76.             dist[j][i]=dist[j-1][i]+dist[j-1][t];
  77.         }
  78.     }
  79. }
  80.  
  81. void pre()
  82. {
  83.     dfs(1,0);
  84.     if(!st.empty())
  85.     {
  86.         ++compCount;
  87.         while(!st.empty())
  88.         {
  89.             int u=st.top(); st.pop();
  90.             compID[u]=compCount;
  91.         }
  92.     }
  93.     foru(i,1,n)
  94.     {
  95.         for(pair<int,int> pa:adj[i])
  96.         {
  97.             int j=pa.fi;
  98.             int u=compID[i], v=compID[j];
  99.             if(u!=v) adjTree[u].pb({v,1});
  100.         }
  101.     }
  102.     buildLCA();
  103. }
  104.  
  105. int calc(int u, int v)
  106. {
  107.     u=compID[u]; v=compID[v];
  108.     if(u==v) return 0;
  109.     if(h[u]>h[v]) swap(u,v);
  110.     int k=h[v]-h[u],ans=0;
  111. //    cout<<u<<' '<<v<<' '<<k<<el;
  112.     ford(j,logn,0)
  113.     {
  114.         if(BIT(k,j))
  115.         {
  116.             ans+=dist[j][v];
  117.             v=jump[j][v];
  118. //            cout<<j<<' '<<v<<el;
  119.         }
  120.     }
  121. //    cout<<el;
  122. //    cout<<u<<' '<<v<<el;
  123.     if(u==v) return ans;
  124.     ford(j,logn,0)
  125.     {
  126.         if(jump[j][u]!=jump[j][v])
  127.         {
  128.             ans+=dist[j][v]+dist[j][u];
  129.             u=jump[j][u]; v=jump[j][v];
  130.         }
  131.     }
  132.     return ans+dist[0][u]+dist[0][v];
  133. }
  134.  
  135. int main()
  136. {
  137.     fastio
  138.     if(fopen(FILE ".inp","r"))
  139.     {
  140.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out","w",stdout);
  141.     }
  142.     cin>>n>>m;
  143.     foru(i,1,m)
  144.     {
  145.         int u,v; cin>>u>>v;
  146.         adj[u].pb({v,i});
  147.         adj[v].pb({u,i});
  148.     }
  149.     pre();
  150.     cin>>q;
  151.     while(q--)
  152.     {
  153.         int u,v; cin>>u>>v;
  154.         cout<<calc(u,v)<<el;
  155.     }
  156.  
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0.01s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zXy9Ky
language:
C++14 (gcc 8.3)
created:
6 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!