fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. constexpr bool typetest = 0;
  9. constexpr int N = 1e5 + 5;
  10. int n, m, q;
  11. vector<pair<int, int>> adj[N];
  12. int low[N], num[N], l = 0;
  13. int com[N];
  14. bool isBridge[N];
  15.  
  16. vector<int> nadj[N];
  17. int par[N][17];
  18. int ranks[N];
  19. int in[N], out[N];
  20.  
  21. void Read()
  22. {
  23.     cin >> n >> m >> q;
  24.  
  25.     for(int i = 1; i <= m; ++i)
  26.     {
  27.         int u,v;
  28.         cin >> u >> v;
  29.         adj[u].emplace_back(v, i);
  30.         adj[v].emplace_back(u, i);
  31.     }
  32. }
  33.  
  34. void dfs(int v, int p)
  35. {
  36.     low[v] = num[v] = ++l;
  37.     for(auto i : adj[v])
  38.         if(i.second != p) 
  39.         {
  40.             if(num[i.first])
  41.             {
  42.                 low[v] = min(low[v], num[i.first]);
  43.             }
  44.             else 
  45.             {
  46.                 dfs(i.first, i.second);
  47.                 low[v] = min(low[v], low[i.first]);
  48.  
  49.                 // Bridge
  50.                 if(low[i.first] > num[v])
  51.                 {
  52.                     isBridge[i.second] = true;
  53.                 }
  54.             }
  55.         }
  56. }
  57.  
  58. void dfs_com(int v)
  59. {
  60.     com[v] = l;
  61.     for(auto i : adj[v])
  62.         if(!com[i.first] && !isBridge[i.second]) {
  63.             dfs_com(i.first);
  64.         }
  65. }
  66.  
  67. void _dfs(int v)
  68. {
  69.     in[v] = ++l;
  70.  
  71.     for(int i = 1; i < 17; ++i)
  72.         par[v][i] = par[par[v][i - 1]][i - 1];
  73.  
  74.     for(auto i : nadj[v])
  75.         if(!ranks[i])
  76.         {
  77.             ranks[i] = ranks[v] + 1;
  78.             par[i][0] = v;
  79.             _dfs(i);
  80.         }
  81.  
  82.     out[v] = l;
  83. }
  84.  
  85. int LCA(int u, int v) {
  86.     if(ranks[u] < ranks[v])
  87.         swap(u, v);
  88.  
  89.     for(int i = 16; ~i; --i)
  90.         if(ranks[par[u][i]] >= ranks[v])
  91.             u = par[u][i];
  92.  
  93.     for(int i = 16; ~i; --i)
  94.         if(par[u][i] != par[v][i])
  95.         {
  96.             u = par[u][i];
  97.             v = par[v][i];
  98.         }
  99.  
  100.     return u == v ? u : par[u][0];
  101. }
  102.  
  103. int In(int x, int y) {
  104.     return in[x] <= in[y] && in[y] <= out[x];
  105. }
  106.  
  107. int Get(int x, int y, int z, int t) {
  108.     if(!In(x, z) && !In(z, x))
  109.         return 0;
  110.  
  111.     for(int i = 16; ~i; --i)
  112.         if(par[t][i] != 0 && !In(par[t][i], y))
  113.             t = par[t][i];
  114.  
  115.     if(!In(t, y)) t = par[t][0];
  116.     // cout << x << " " << y << " " << z << " " << t << "\n";
  117.  
  118.     return max(0, ranks[t] - max(ranks[x], ranks[z]));
  119. }
  120.  
  121. void Solve()
  122. {
  123.     dfs(1, -1);
  124.  
  125.     l = 0;
  126.     for(int i = 1; i <= n; ++i)
  127.         if(!com[i])
  128.         {
  129.             ++l;
  130.             dfs_com(i);
  131.         }
  132.  
  133.     for(int i = 1; i <= n; ++i)
  134.         for(auto j : adj[i])
  135.             if(com[i] < com[j.first])
  136.             {
  137.                 nadj[com[i]].emplace_back(com[j.first]);
  138.                 nadj[com[j.first]].emplace_back(com[i]);
  139.             }
  140.  
  141.     ranks[1] = 1;
  142.     l = 0;
  143.     _dfs(1);
  144.  
  145.     while(q--) {
  146.         int a, b, c, d;
  147.         cin >> a >> b >> c >> d;
  148.         a = com[a];
  149.         b = com[b];
  150.         c = com[c];
  151.         d = com[d];
  152.  
  153.         int lcaAB = LCA(a, b);
  154.         int lcaCD = LCA(c, d);
  155.  
  156.         int ans = ranks[c] + ranks[d] - 2 * ranks[lcaCD];
  157.         // cerr << ans << " ";
  158.         ans -= Get(lcaAB, a, lcaCD, c);
  159.         ans -= Get(lcaAB, a, lcaCD, d);
  160.         ans -= Get(lcaAB, b, lcaCD, c);
  161.         ans -= Get(lcaAB, b, lcaCD, d);
  162.  
  163.         cout << ans << "\n";
  164.     }
  165. }
  166.  
  167. int32_t main()
  168. {
  169.     ios::sync_with_stdio(0);
  170.     cin.tie(0);
  171.     cout.tie(0);
  172.  
  173.     if (fopen("tests.inp", "r"))
  174.     {
  175.         freopen("test.inp", "r", stdin);
  176.         freopen("test.out", "w", stdout);
  177.     }
  178.  
  179.     int t(1);
  180.     if (typetest)
  181.         cin >> t;
  182.  
  183.     for (int _ = 1; _ <= t; ++_)
  184.     {
  185.         // cout << "Case #" << _ << endl;
  186.         Read();
  187.         Solve();
  188.     }
  189.     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  190. }
  191.  
  192. /*
  193. Input:
  194. 1
  195. abcahsdfaw
  196. 1
  197. q i
  198.  
  199. Output:
  200. 9
  201. */
  202.  
Success #stdin #stdout 0.01s 8796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E0515h
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!