結果

問題 No.768 Tapris and Noel play the game on Treeone
コンテスト
ユーザー lumc_
提出日時 2018-01-16 01:13:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,652 bytes
コンパイル時間 1,250 ms
コンパイル使用メモリ 121,800 KB
実行使用メモリ 35,632 KB
最終ジャッジ日時 2024-09-25 06:14:15
合計ジャッジ時間 7,673 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

// see https://github.com/LumaKernel/vimfiles/tree/master/snippets/cp-cpp/temp.snip
const bool DEBUG = 1;
/// --- .lumrc Template {{{ ///
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>
#include <cassert>
#include <functional>

#include <unordered_map>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = tuple<ll, ll>;
using P3 = tuple<ll, ll, ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VP = vector<P>;
using VS = vector<string>;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define FORI(i,a,b) for(int i=int(a);i<=int(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPI(i,n) FORI(i,0,n)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define RFORI(i,a,b) for(int i=int(b);i>=int(a);--i)
#define RREP(i,n) RFOR(i,0,n)
#define RREPI(i,n) RFORI(i,0,n)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique(ALL(a)),(a).end())
#define PB push_back
#define EACH(i,c) REP(i,(c).size())
#define REACH(i,c) RREP(i,(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))

#define BR cout<<"\n";

#define dump(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)<<"\n";
#define dump2(x,y) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)\
  <<" , "<<#y<<"="<<(y)<<"\n";
#define dump3(x,y,z) if(DEBUG)cerr<<"["<<__LINE__<<"] "<<#x<<"="<<(x)\
  <<" , "<<#y<<"="<<(y)\
<<" , "<<#z<<"="<<(z)<<"\n";

#define SAY(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<(x)<<"\n";

#define YES(x) cout<<((x)?"YES":"NO")<<"\n";
#define Yes(x) cout<<((x)?"Yes":"No")<<"\n";
#define yes(x) cout<<((x)?"yes":"no")<<"\n";

inline int omajinai_int_in(){omajinai;int n;cin>>n;return n;}
inline ll omajinai_ll_in(){omajinai;ll n;cin>>n;return n;}
inline string omajinai_string_in(){omajinai;string n;cin>>n;return n;}
inline int int_in(){int n;cin>>n;return n;}
inline ll ll_in(){ll n;cin>>n;return n;}
inline string string_in(){string n;cin>>n;return n;}
#define oini omajinai_int_in()
#define oinl omajinai_ll_in()
#define oins omajinai_string_in()
#define ini int_in()
#define inl ll_in()
#define ins string_in()

#define isInside(y,x) (0<=(y)&&(y)<h&&0<=(x)&&(x)<w)

#define fi(x) (get<0>(x))
#define se(x) (get<1>(x))
#define th(x) (get<2>(x))
#define fo(x) (get<3>(x))
#define fif(x) (get<4>(x))

template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; EACH(i, v) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }

template <typename T> inline void smax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void smin(T &a, T b) { a = a < b ? a : b; }

/// }}}--- ///

constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr int MOD = 1e9+7;

const int N = 1e5;

VI g[N];

unordered_map<int, bool> dp[N];

// メモ化再帰
// parent == -1 => i is root
bool dfs(int i, int parent) {
  if(EXIST(dp[i], parent)) return dp[i][parent];
  bool flag = false;
  for(int j : g[i]) {
    if(j == parent) continue;
    flag |= dfs(j, i);
  }
  return dp[i][parent] = !flag;
}

int ans[N];
int main() {
  int n = ini;
  // グラフ構築
  REP(i, n-1) {
    int a = ini - 1, b = ini - 1;
    g[a].PB(b);
    g[b].PB(a);
  }

  // iを根としてwinningなら追加
  int k = 0;
  REP(i, n) {
    if(dfs(i, -1)) ans[k++] = i;
  }

  // output
  cout << k << endl;
  REP(i, k) {
    cout << ans[i]+1 << endl;
  }
}

//
0