結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2019-01-10 06:52:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 246 ms / 2,000 ms |
コード長 | 1,609 bytes |
コンパイル時間 | 2,582 ms |
コンパイル使用メモリ | 76,616 KB |
実行使用メモリ | 17,752 KB |
最終ジャッジ日時 | 2024-11-24 01:06:07 |
合計ジャッジ時間 | 5,562 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include<cstdio>#include<cstring>#include<vector>#include<queue>#include<stack>#include<algorithm>#include<cmath>#include<climits>#include<string>#include<set>#include<numeric>#include<map>#include<iostream>using namespace std;#define rep(i,n) for(int i = 0;i<((int)(n));i++)#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)typedef long long ll;typedef pair<ll, ll> mp;ll mod = 1e9+7;//LLONG_MIN/*グラフに必敗に繋がる辺の数をメモしておくと計算量短縮grundyは0か非0かだけが意味を持つ相手に0を押し付ければ勝てる*/ll n,lose[100010]={},visit[100010]={};vector<ll> v[100010],grundy[100010],ans;ll dfs(ll par,ll p,ll edge_id){if(par!=-1){if(lose[p]>=2)return 1;//1手で0に行けるので}else{if(lose[p]>=1){return 1;//1手で0に行けるので}else if(visit[p]==v[p].size())return 0;}ll lose_num=0;rep(i,v[p].size()){if(v[p][i]==par)continue;if(grundy[p][i]==-1){grundy[p][i]=dfs(p,v[p][i],i);if(grundy[p][i]==0)lose[p]++;visit[p]++;}if(grundy[p][i]==0)lose_num=1;}return lose_num;}int main(void){cin>>n;rep(i,n-1){ll a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);grundy[a].push_back(-1);grundy[b].push_back(-1);}reg(i,1,n){if(dfs(-1,i,0)==0)ans.push_back(i);//最初においた場所が、相手がどう置こうが必敗になる場所}cout<<ans.size()<<endl;rep(i,ans.size())cout<<ans[i]<<endl;return 0;}