結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー | cureskol |
提出日時 | 2021-10-12 15:26:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 2,081 bytes |
コンパイル時間 | 2,009 ms |
コンパイル使用メモリ | 179,228 KB |
実行使用メモリ | 10,916 KB |
最終ジャッジ日時 | 2024-09-17 01:30:31 |
合計ジャッジ時間 | 6,343 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 67 ms
7,424 KB |
testcase_08 | AC | 32 ms
5,376 KB |
testcase_09 | AC | 40 ms
5,760 KB |
testcase_10 | AC | 29 ms
5,376 KB |
testcase_11 | AC | 123 ms
9,728 KB |
testcase_12 | AC | 127 ms
9,856 KB |
testcase_13 | AC | 120 ms
9,600 KB |
testcase_14 | AC | 113 ms
9,600 KB |
testcase_15 | AC | 125 ms
10,112 KB |
testcase_16 | AC | 123 ms
9,984 KB |
testcase_17 | AC | 130 ms
10,112 KB |
testcase_18 | AC | 106 ms
10,768 KB |
testcase_19 | AC | 103 ms
10,916 KB |
testcase_20 | AC | 108 ms
10,496 KB |
testcase_21 | AC | 100 ms
10,112 KB |
20evil_special_uni1.txt | AC | 124 ms
9,984 KB |
20evil_special_uni2.txt | AC | 116 ms
9,728 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0;i<(n);i++)#define RREP(i,n) for(int i=(n-1);i>=0;i--)#define ALL(v) v.begin(),v.end()//key_t:辺固有の情報 頂点固有の情報はラムダの方でキャプチャさせる//sum_t:計算結果template<typename key_t,typename sum_t=key_t>struct ReRooting{struct Edge {int from,to;key_t cost;sum_t dp1,dp2;//dp1:部分木の内容//dp2:e=g[idx][i]の時、g[idx][0,i)のdp1の累積が入る};using S=function<sum_t(sum_t,Edge)>;using M=function<sum_t(sum_t,sum_t)>;vector<vector<Edge>> g;const S score;const M merge;const sum_t id;vector<sum_t> dp1,dp2;ReRooting(int n,const S &score,const M &merge,const sum_t &id=sum_t{}):g(n),score(score),merge(merge),id(id),dp1(n,id),dp2(n,id){}void add_edge(int u,int v,const key_t &c){g[u].emplace_back(Edge{u,v,c,id,id});g[v].emplace_back(Edge{v,u,c,id,id});}void add_directed_edge(int u,int v,const key_t &c){g[u].emplace_back(Edge{u,v,c,id,id});}void dfs1(int idx,int pre){for(auto &e:g[idx])if(e.to!=pre){dfs1(e.to,idx);e.dp1=score(dp1[e.to],e);dp1[idx]=merge(dp1[idx],e.dp1);}}void dfs2(int idx,int pre,sum_t top){sum_t now=id;for(auto &e:g[idx]){e.dp2=now;if(e.to==pre)e.dp1=score(top,e);now=merge(now,e.dp1);}dp2[idx]=now;now=id;reverse(g[idx].begin(),g[idx].end());for(auto &e:g[idx]){if(e.to!=pre)dfs2(e.to,idx,merge(e.dp2,now));now=merge(now,e.dp1);}}vector<sum_t> build(){dfs1(0,-1);dfs2(0,-1,id);return dp2;}};int main(){int n;cin>>n;auto score=[](bool x,auto e){return !x;};auto merge=[](bool x,bool y){return x&y;};ReRooting<bool> g(n,score,merge,1);REP(_,n-1){int u,v;cin>>u>>v;u--;v--;g.add_edge(u,v,0);}auto ans=g.build();vector<int> fans;REP(i,n)if(ans[i])fans.push_back(i);cout<<fans.size()<<'\n';for(int p:fans)cout<<p+1<<'\n';}