fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define maxn 400005
  4. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5.  
  6. using namespace std;
  7.  
  8. int Timer=0,num[maxn],low[maxn];
  9. int used[maxn],numChild[maxn],cut[maxn];
  10. int bridge[maxn],high_bridge[maxn],up_bridge[maxn][25];
  11. int high[maxn],up[maxn][25],val[maxn];
  12. int par[maxn],n,m,q;
  13. vector<pair<int,int>> adj[maxn];
  14. vector<int> adj_bridge[maxn],adj_bc[maxn];
  15. vector<int> st;
  16. int seen=1,vis[maxn];
  17. pair<int,int> edge[maxn];
  18. int cnt_node=0,mp[maxn];
  19.  
  20. void dfs(int u,int idpar){
  21.     num[u]=low[u]=++Timer;
  22.     for(auto [v,id] : adj[u]){
  23.         if(id==idpar) continue;
  24.         if(!used[id]){
  25.             used[id]=1;
  26.             if(!num[v]){
  27.                 st.push_back(id);
  28.                 numChild[u]++;
  29.                 dfs(v,id);
  30.                 low[u]=min(low[u],low[v]);
  31.  
  32.                 if(low[v] > num[u]) bridge[id]=1;
  33.  
  34.                 if(low[v] >= num[u]){
  35.                     if(idpar==0){
  36.                         if(numChild[u] > 1) cut[u]=1;
  37.                     } else cut[u]=1;
  38.  
  39.                     int node=++cnt_node+n;
  40.                     seen++;
  41.                     while(1){
  42.                         int e=st.back(); st.pop_back();
  43.                         int U=edge[e].first;
  44.                         int V=edge[e].second;
  45.  
  46.                         if(vis[U]!=seen){
  47.                             adj_bc[U].push_back(node);
  48.                             adj_bc[node].push_back(U);
  49.                             vis[U]=seen;
  50.                         }
  51.                         if(vis[V]!=seen){
  52.                             adj_bc[V].push_back(node);
  53.                             adj_bc[node].push_back(V);
  54.                             vis[V]=seen;
  55.                         }
  56.                         if(e==id) break;
  57.                     }
  58.                 }
  59.             } else{
  60.                 st.push_back(id);
  61.                 low[u]=min(low[u],num[v]);
  62.             }
  63.         }
  64.     }
  65. }
  66.  
  67. void dfs_node(int u,int p){
  68.     for(int v: adj_bc[u]){
  69.         if(v==p) continue;
  70.         high[v]=high[u]+1;
  71.         up[v][0]=u;
  72.         val[v]+=val[u];
  73.         dfs_node(v,u);
  74.     }
  75. }
  76.  
  77. int lca(int u,int v){
  78.     if(high[u]<high[v]) swap(u,v);
  79.     int diff=high[u]-high[v];
  80.     for(int j=20;j>=0;j--) if(diff>>j&1) u=up[u][j];
  81.  
  82.     if(u==v) return u;
  83.  
  84.     for(int j=20;j>=0;j--){
  85.         if(up[u][j]!=up[v][j]){
  86.             u=up[u][j];
  87.             v=up[v][j];
  88.         }
  89.     }
  90.     return up[u][0];
  91. }
  92.  
  93. int find_par(int u){
  94.     return u==par[u]?u:par[u]=find_par(par[u]);
  95. }
  96.  
  97. void join(int u,int v){
  98.     u=find_par(u); v=find_par(v);
  99.     if(u!=v) par[v]=u;
  100. }
  101.  
  102. void dfs_bridge(int u,int p){
  103.     for(int v: adj_bridge[u]){
  104.         if(v==p) continue;
  105.         high_bridge[v]=high_bridge[u]+1;
  106.         up_bridge[v][0]=u;
  107.         dfs_bridge(v,u);
  108.     }
  109. }
  110.  
  111. int lca_bridge(int u,int v){
  112.     if(high_bridge[u]<high_bridge[v]) swap(u,v);
  113.     int diff=high_bridge[u]-high_bridge[v];
  114.     for(int j=20;j>=0;j--) if(diff>>j&1) u=up_bridge[u][j];
  115.  
  116.     if(u==v) return u;
  117.  
  118.     for(int j=20;j>=0;j--){
  119.         if(up_bridge[u][j]!=up_bridge[v][j]){
  120.             u=up_bridge[u][j];
  121.             v=up_bridge[v][j];
  122.         }
  123.     }
  124.     return up_bridge[u][0];
  125. }
  126.  
  127. signed main(){
  128.     itachi
  129.     cin>>n>>m>>q;
  130.  
  131.     for(int i=1;i<=m;i++){
  132.         int u,v; cin>>u>>v;
  133.         adj[u].push_back({v,i});
  134.         adj[v].push_back({u,i});
  135.         edge[i]={u,v};
  136.     }
  137.  
  138.     for(int i=1;i<=n;i++){
  139.         if(!num[i]){
  140.             st.clear();
  141.             dfs(i,0);
  142.         }
  143.     }
  144.  
  145.     for(int i=1;i<=n;i++) val[i]=1;
  146.  
  147.     for(int i=1;i<=n+cnt_node;i++){
  148.         if(!high[i]){
  149.             high[i]=1;
  150.             dfs_node(i,0);
  151.         }
  152.     }
  153.  
  154.     for(int j=1;j<=20;j++)
  155.         for(int i=1;i<=n+cnt_node;i++)
  156.             up[i][j]=up[up[i][j-1]][j-1];
  157.  
  158.     for(int i=1;i<=n;i++) par[i]=i;
  159.  
  160.     for(int i=1;i<=m;i++){
  161.         if(!bridge[i]){
  162.             join(edge[i].first,edge[i].second);
  163.         }
  164.     }
  165.  
  166.     int cnt=0;
  167.     for(int i=1;i<=n;i++){
  168.         int r=find_par(i);
  169.         if(!mp[r]) mp[r]=++cnt;
  170.     }
  171.  
  172.     for(int i=1;i<=m;i++){
  173.         if(bridge[i]){
  174.             int a=mp[find_par(edge[i].first)];
  175.             int b=mp[find_par(edge[i].second)];
  176.             adj_bridge[a].push_back(b);
  177.             adj_bridge[b].push_back(a);
  178.         }
  179.     }
  180.  
  181.     for(int i=1;i<=cnt;i++){
  182.         if(!high_bridge[i]){
  183.             high_bridge[i]=1;
  184.             dfs_bridge(i,0);
  185.         }
  186.     }
  187.  
  188.     for(int j=1;j<=20;j++)
  189.         for(int i=1;i<=cnt;i++)
  190.             up_bridge[i][j]=up_bridge[up_bridge[i][j-1]][j-1];
  191.  
  192.     while(q--){
  193.         int s,t; cin>>s>>t;
  194.  
  195.         int w=lca(s,t);
  196.         cout<<val[s]+val[t]-2*val[w]+(w<=n)<<' ';
  197.  
  198.         int u=mp[find_par(s)];
  199.         int v=mp[find_par(t)];
  200.         w=lca_bridge(u,v);
  201.  
  202.         cout<<high_bridge[u]+high_bridge[v]-2*high_bridge[w]<<'\n';
  203.     }
  204.     return 0;
  205. }
  206.  
Success #stdin #stdout 0.01s 34220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c15KWQ
language:
C++14 (gcc 8.3)
created:
2 days 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!