Submission #1635970

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct edge{int to, cost;};

int n, d[1010][1010];
vector<edge> g[100010];

void dijkstra(int s) {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  REP(i, n) d[s][i] = LLINF;
  d[s][s] = 0;
  que.push(PII{0, s});

  while(que.size()) {
    PII p = que.top(); que.pop();
    int v = p.second;
    if(d[s][v] < p.first) continue;
    for(edge e: g[v]) {
      if(d[s][e.to] > d[s][v] + e.cost) {
        d[s][e.to] = d[s][v] + e.cost;
        que.push(PII{d[s][e.to], e.to});
      }
    }
  }
}

signed main(void)
{
  cin >> n;
  int m;
  cin >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    g[a].PB({b,1});
    g[b].PB({a,1});
  }
  REP(i, n) dijkstra(i);
  int ma1 = 0, mi1 = INF;
  // REP(i, n) {
  //   REP(j, n) {
  //     cout << d[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  REP(i, n) {
    int ma = 0;
    REP(j, n) {
      if(i == j || d[i][j] == LLINF) continue;
      chmax(ma, d[i][j]);
    }
    chmax(ma1, ma);
    chmin(mi1, ma);
  }
  // cout << mi1 << "," << ma1 << endl;

  cin >> n;
  cin >> m;
  REP(i, n) g[i].clear();
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    g[a].PB({b,1});
    g[b].PB({a,1});
  }
  memset(d, 0, sizeof(d));
  REP(i, n) dijkstra(i);
  int ma2 = 0, mi2 = INF;
  REP(i, n) {
    int ma = 0;
    REP(j, n) {
      if(i == j || d[i][j] == LLINF) continue;
      chmax(ma, d[i][j]);
    }
    chmax(ma2, ma);
    chmin(mi2, ma);
  }
  // cout << mi2 << "," << ma2 << endl;

  cout << max({ma1, ma2, mi1 + mi2 + 1}) << " " << ma1 + ma2 + 1  << endl;

  return 0;
}

Submission Info

Judge Result