Tamflexの貯蔵庫

やる気のない備忘録

abc 019

D問題

abc019.contest.atcoder.jp

double sweepというアルゴリズムを用いる(らしい)
任意の頂点 iから最も離れた頂点を v_iとした場合、木の直径は v_iから最も離れた頂点までの距離となる。背理法によって簡単に示せる。
これによって \small 2(N-1)回の検索で直径が計算される。

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  int n; cin >> n;
  int a = 1; ll dist, m = 0, ans = 0;
  FOR(i,2,n)
  {
    cout << "? " << 1 << " " << i << endl;
    cin >> dist;
    a = dist > ans ? i : a;
    ans = max(ans,dist);
  }
  FOR(i,1,n)
  {
    if(i == a) continue;
    cout << "? " << a << " " << i << endl;
    cin >> dist;
    ans = max(ans,dist);
  }
  cout << "! " << ans << endl;
  return 0;
}