結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

void solve1(){
  int n;
  cin>>n;
  cout<<n-2<<endl;
  vector<vector<int>> g(n);
  vector<int> d(n);
  for (int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    g[u].push_back(v);
    g[v].push_back(u);
    d[u]++;
    d[v]++;
  }
  priority_queue<int> q;
  for (int i=0;i<n;i++) if (d[i]==1) q.push(-i);
  vector<int> a;
  while (!q.empty()){
    int v=q.top();q.pop();
    v*=-1;
    for (int u:g[v]){
      if (d[u]>0){
        a.push_back(u+1);
        if (--d[u]==1) q.push(-u);
      }
    }
  }
  for (int i=0;i<n-2;i++) cout<<a[i]<<" \n"[i==n-3];
  cout<<flush;
}

void solve2(){
  int n;
  cin>>n;
  cout<<n-2<<endl;
  vector<int> a(n-2);
  vector<int> d(n,1);
  for (int i=0;i<n-2;i++){
    cin>>a[i],a[i]--;
    d[a[i]]++;
  }
  priority_queue<int> q;
  for (int i=0;i<n;i++){
    if (d[i]==1) q.push(-i);
  }
  vector<pair<int,int>> edge;
  int now=0;
  while (!q.empty()){
    int v=q.top();q.pop();
    v*=-1;
    edge.push_back({v,a[now]});
    if (--d[v]==1) q.push(-v);
    if (--d[a[now]]==1) q.push(-a[now]);
    if (now++==n-3) break;
  }
  vector<int> vec;
  for (int i=0;i<n;i++){
    if (d[i]>0) vec.push_back(i);
  }
  edge.push_back({vec[0],vec[1]});
  for (int i=0;i<n-1;i++) cout<<edge[i].first+1<<" "<<edge[i].second+1<<endl;
}

int main(){
  string s;
  cin>>s;
  if (s=="Alice") solve1();
  if (s=="Bob") solve2();
}
0