結果

問題 No.768 Tapris and Noel play the game on Treeone
ユーザー cureskolcureskol
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0