結果

問題 No.3719 Share the Tree
コンテスト
ユーザー 👑 Nachia
提出日時 2026-09-18 22:12:17
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 120 ms / 2,000 ms
+ 1µs
コード長 1,905 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 639 ms
コンパイル使用メモリ 106,444 KB
実行使用メモリ 6,528 KB
平均クエリ数 2.00
最終ジャッジ日時 2026-09-18 22:12:22
合計ジャッジ時間 4,744 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

V<pair<ll,ll>> from_preufer(ll N, vector<ll> Y){
  V<pair<ll,ll>> res;
  V<ll> cnt(N);
  cnt[N-1] = 1;
  for(ll i=0; i<N-2; i++) cnt[Y[i]]++;
  priority_queue<ll> que;
  for(ll i=0; i<N; i++) if(cnt[i] == 0) que.push(-i);
  for(ll j=0; j<N-2; j++){
    res.emplace_back(Y[j], -que.top());
    que.pop();
    if(--cnt[Y[j]] == 0) que.push(-Y[j]);
  }
  res.emplace_back(N-1, -que.top());
  return res;
}

void Alice(ll N){
  V<pair<ll,ll>> edges(N-1);
  REP(i,N-1){
    ll u,v; cin >> u >> v; u--; v--;
    edges[i] = {u,v};
  }

  V<ll> ans;
  V<ll> used(N);

  REP(i,N-2){
    V<ll> deg(N);
    for(auto [u,v] : edges) if(!used[u] && !used[v]){ deg[u]++; deg[v]++; }
    ll leaf = -1;
    for(ll j=N-2; j>=0; j--) if(deg[j] == 1 && !used[j]) leaf = j;
    for(auto [u,v] : edges) if(!used[u] && !used[v]){
      if(u == leaf){ ans.push_back(v); }
      if(v == leaf){ ans.push_back(u); }
    }
    used[leaf] = 1;
  }
  
  REP(i,N-2){
    if(i) cout << " ";
    cout << (ans[i] + 1);
  } cout << endl;
}

void Bob(ll N){
  V<ll> A(N-2);
  for(auto& a : A){ cin >> a; a--; }
  auto tree = from_preufer(N, A);
  for(auto [u,v] : tree) cout << (u+1) << " " << (v+1) << endl;
}

void testcase(){
  string player; cin >> player;
  ll N; cin >> N;
  cout << (N-2) << endl;
  if(player[0] == 'A') Alice(N); else Bob(N);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // ll T; cin >> T; REP(t,T)
  testcase();
  return 0;
}
0