結果

問題 No.3719 Share the Tree
コンテスト
ユーザー umezo
提出日時 2026-11-01 23:43:02
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 488 ms / 2,000 ms
+ 999µs
コード長 1,828 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,705 ms
コンパイル使用メモリ 353,776 KB
実行使用メモリ 9,776 KB
平均クエリ数 2.00
最終ジャッジ日時 2026-11-01 23:43:15
合計ジャッジ時間 8,483 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_iterator.h:78,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_algobase.h:67,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/algorithm:62,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:53,
                 from main.cpp:1:
In function 'constexpr _Tp* std::construct_at(_Tp*, _Args&& ...) [with _Tp = int; _Args = {const int&}]',
    inlined from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/alloc_traits.h:676:21,
    inlined from 'constexpr void std::vector<_Tp, _Alloc>::_M_realloc_append(_Args&& ...) [with _Args = {const int&}; _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/vector.tcc:586:26,
    inlined from 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:1427:21,
    inlined from 'V<int> PruferEncode(VV<int>&)' at main.cpp:30:18:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_construct.h:110:16: warning: 'v' may be used uninitialized [-Wmaybe-uninitialized]
  110 |         return ::new(__loc) _Tp(std::forward<_Args>(__args)...);
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'V<int> PruferEncode(VV<int>&)':
main.cpp:23:9: note: 'v' was declared here
   23 |     int v;
      |         ^

ソースコード

diff #
raw source code 

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
template <class T> using V=vector<T>;
template <class T> using VV=V<V<T>>;
using u128=__int128_t;
using ll=long long;

V<int> PruferEncode(VV<int>& G){
  int n=G.size();
  V<int> ret,deg(n);
  rep(v,n) deg[v]=G[v].size();
  
  priority_queue<int,V<int>,greater<int>> que;
  rep(v,n) if(deg[v]==1) que.push(v);
  
  rep(i,n-2){
    auto u=que.top(); que.pop();
    int v;
    for(auto nv:G[u]){
      if(deg[nv]){
        v=nv;
        break;
      }
    }
    ret.push_back(v);
    deg[u]=0;
    deg[v]--;
    if(deg[v]==1) que.push(v);
  }
  return ret;
}

V<pair<int,int>> PruferDecode(V<int>& P){
  int n=P.size()+2;
  V<int> cnt(n);
  for(auto v:P) cnt[v]++;
  
  priority_queue<int,V<int>,greater<int>> que;
  rep(v,n) if(cnt[v]==0) que.push(v);
  
  V<pair<int,int>> ret;
  rep(i,n-2){
    auto u=que.top(); que.pop();
    int v=P[i];
    ret.push_back(make_pair(u,v));
    cnt[v]--;
    if(cnt[v]==0) que.push(v);
  }
  auto u=que.top(); que.pop();
  auto v=que.top(); que.pop();
  ret.push_back(make_pair(u,v));
  return ret;
}
 
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  string s;
  int n;
  cin>>s>>n;
  cout<<n-2<<endl;
  if(s=="Alice"){
    VV<int> G(n);
    rep(i,n-1){
      int u,v;
      cin>>u>>v;
      u--,v--;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    auto P=PruferEncode(G);
    rep(i,n-2){
      if(i) cout<<" ";
      cout<<P[i]+1;
    }
    cout<<endl;
  }
  else{
    V<int> P(n-2);
    rep(i,n-2){
      cin>>P[i];
      P[i]--;
    }
    auto G=PruferDecode(P);
    rep(i,n-1) cout<<G[i].first+1<<" "<<G[i].second+1<<endl;
  }
  
  return 0;
}
0