fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 2e5 + 5;
  5. int n, m, q, h[N], par[N][20], tin[N], tout[N], timer = 0;
  6. vector<int> G[N];
  7. vector<pair<int, int>> adj[N];
  8. stack<int> s;
  9. int num[N], low[N], scc[N], cou = 0, cnt = 0;
  10.  
  11. void tarjan(int u, int old) {
  12.     num[u] = low[u] = ++cou;
  13.     s.push(u);
  14.     for(auto [v, id] : adj[u]) {
  15.         if (old == id) continue;
  16.         if (num[v]) low[u] = min(low[u], num[v]);
  17.         else {
  18.             tarjan(v, id);
  19.             low[u] = min(low[u], low[v]);
  20.         }
  21.     }
  22.     if (num[u] == low[u]) {
  23.         int v;
  24.         cnt++;
  25.         do {
  26.             v = s.top();
  27.             s.pop();
  28.             scc[v] = cnt;
  29.         } while(v != u);
  30.     }
  31. }
  32.  
  33. void dfs(int u) {
  34.     tin[u] = ++timer;
  35.     for(int j = 1; j <= 19; j++) par[u][j] = par[par[u][j - 1]][j - 1];
  36.     for(int v : G[u]) if (v != par[u][0]) {
  37.         par[v][0] = u;
  38.         h[v] = h[u] + 1;
  39.         dfs(v);
  40.     }
  41.     tout[u] = timer;
  42. }
  43.  
  44. int LCA(int u, int v) {
  45.     if (h[u] < h[v]) swap(u, v);
  46.     int s = h[u] - h[v];
  47.     for(int j = 0; j < 20; j++) if ((s >> j) & 1)
  48.         u = par[u][j];
  49.     if (u == v) return u;
  50.     for(int j = 19; j >= 0; j--) if (par[u][j] != par[v][j]) {
  51.         u = par[u][j];
  52.         v = par[v][j];
  53.     }
  54.     return par[u][0];
  55. }
  56.  
  57. int dist(int u, int v) {
  58.     return h[u] + h[v] - 2 * h[LCA(u, v)];
  59. }
  60.  
  61. bool in(int u, int v){
  62.     return tin[u] <= tin[v] && tout[v] <= tout[u];
  63. }
  64.  
  65. int f(int x, int y, int u, int v) {
  66.     if (h[x] > h[u]) swap(x, u), swap(y, v);
  67.     if (in(x, u) && in(u, y)) return max(0, h[LCA(v, y)] - h[u]);
  68.     return 0;
  69. }
  70.  
  71. int main() {
  72.  
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0); cout.tie(0);
  75.     cin >> n >> m >> q;
  76.     for(int i = 0; i < m; i++) {
  77.         int u, v;
  78.         cin >> u >> v;
  79.         adj[u].emplace_back(v, i);
  80.         adj[v].emplace_back(u, i);
  81.     }
  82.     for(int i = 1; i <= n; i++) if (!num[i]) tarjan(i, -1);
  83.     for(int i = 1; i <= n; i++) {
  84.         for(auto [v,id] : adj[i]) if (scc[i] != scc[v])
  85.             G[scc[i]].push_back(scc[v]);
  86.     }
  87.  
  88.     dfs(1);
  89.     while(q--) {
  90.         int a, b, c, d;
  91.         cin >> a >> b >> c >> d;
  92.         a = scc[a]; b = scc[b]; c = scc[c]; d = scc[d];
  93.         int u = LCA(a, b);
  94.         int v = LCA(c, d);
  95.         cout << dist(c, d) - (f(u, a, v, c) + f(u, b, v, c) + f(u, a, v, d) + f(u, b, v, d)) << '\n';
  96.     }
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 15928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C8nLFz
language:
C++14 (gcc 8.3)
created:
1 day 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!