fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define forr(i, l, r) for (int i=l;i<=r;i++)
  3. #define ll long long
  4. #define pii pair <long long, int>
  5. #define f first
  6. #define s second
  7. #define ii long long
  8. #define iii pair <pii, int>
  9. #define endl '\n'
  10. using namespace std;
  11.  
  12. int const N=5e4 + 1;
  13. vector <pii> adj[N];
  14. int n, m, k;
  15. ll d[N];
  16. ll cnt[N], a[N], b[N];
  17. ll run[N];
  18. void inp()
  19. {
  20.     cin >> n >> m;
  21.     forr(i, 1, m)
  22.     {
  23.         ll u, v, w;
  24.        cin >> u >> v;
  25.        u++, v++;
  26.         adj[u].push_back({v, 1});
  27.         adj[v].push_back({u, 1});
  28.     }
  29.     cin >> k;
  30.  
  31.     forr(i, 1, k) {
  32.     cin >> a[i] >> b[i];
  33.     a[i]++, b[i]++;
  34. //    cout << a[i] << " " << b[i] << endl;
  35.     }
  36. }
  37. void bfs1(int u1)
  38. {
  39.     queue <int> q;
  40.     forr(i, 1, n)
  41.     d[i] = -1;
  42.     q.push(u1);
  43.     d[u1] = 1;
  44.     cnt[u1] = 1;
  45.     while (!q.empty()) {
  46.             int u = q.front();
  47.     q.pop();
  48.     for (auto[v, w] : adj[u])
  49.         if (d[v] == -1)
  50.         {
  51.              d[v] = d[u] + 1;
  52.              cnt[v] = cnt[u];
  53.             q.push(v);
  54.         }
  55.         else if (d[v] == d[u] + 1)
  56.         {
  57.             cnt[v] += cnt[u];
  58.         }
  59. }
  60. }
  61. ll e[2002][5002];
  62. pii ps(ll x, ll y)
  63. {
  64.     return {x/__gcd(x, y), y/__gcd(x, y)};
  65. }
  66. bool cmp(iii a, iii b)
  67. {
  68.  
  69.         if  (a.f.f * b.f.s == a.f.s * b.f.f)
  70.             return a.s < b.s;
  71.             return a.f.f * b.f.s < a.f.s * b.f.f;
  72. }
  73. pii cong(pii a, pii b)
  74. {
  75.     ll o = a.f * b.s;
  76.     ll o2 = b.f * a.s;
  77.     return ps(o + o2, a.s * b.s);
  78. }
  79. void bfs(ll u1, int i)
  80. {
  81.     queue <int> q;
  82.     q.push(u1);
  83.     e[i][u1] = cnt[u1];
  84.     while (!q.empty()) {
  85.             int u = q.front();
  86.     q.pop();
  87.     for (auto[v, w] : adj[u])
  88.         if (d[v] + w == d[u])
  89.         {
  90. //            cout << i << " " << u << " " << v << endl;
  91.             e[i][v] = cnt[v];
  92.             q.push(v);
  93.         }
  94. }
  95. }
  96. iii ans[N];
  97. int main()
  98. {
  99.     freopen("traincentre.inp", "r", stdin);
  100.     freopen("traincentre.out", "w", stdout);
  101.      ios_base::sync_with_stdio(false);
  102.     cin.tie(NULL);
  103. inp();
  104. forr(i, 1, k)
  105. {
  106.     bfs1(a[i]);
  107.     run[i] = cnt[b[i]];
  108. //    forr(j, 1, n)
  109. //    cout << i <<" " << j << " " << cnt[j] << endl;
  110. //    cout << run[i] << " " << i << endl;
  111.     bfs(b[i], i);
  112.     forr(z, 1, n) cnt[z] = 0, d[z] = 0;
  113. }
  114. forr(j, 1, n) {
  115.  pii x = {0, 1};
  116. forr(i, 1, k) {
  117.     x = cong(x, ps(e[i][j], run[i]));
  118. //    cout << e[i][j] << " " << i << ' ' << j - 1 << endl;
  119. }
  120. //cout << x.f << " " << x.s << " " << j << endl;
  121. //cout << x.f << " " << x.s << " " << j << endl;
  122. ans[j] = {x, j};
  123. }
  124. sort(ans + 1, ans + 1 + n, cmp);
  125. cout << ans[n].s - 1;
  126.  
  127. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YM5IeH
language:
C++14 (gcc 8.3)
created:
5 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!