結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2022-07-28 15:57:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 188 ms / 2,000 ms |
コード長 | 6,674 bytes |
コンパイル時間 | 1,363 ms |
コンパイル使用メモリ | 132,084 KB |
実行使用メモリ | 23,136 KB |
最終ジャッジ日時 | 2024-07-18 06:45:35 |
合計ジャッジ時間 | 5,572 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#include <climits>#include <cstring>#include <cassert>using namespace std;//using namespace atcoder;#define REP(i, n) for (int i=0; i<(n); ++i)#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)#define FOR(i, a, n) for (int i=(a); i<(n); ++i)#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)#define SZ(x) ((int)(x).size())#define ALL(x) (x).begin(),(x).end()#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;template<class T>ostream &operator<<(ostream &os, const vector<T> &v) {os << "[";REP(i, SZ(v)) {if (i) os << ", ";os << v[i];}return os << "]";}template<class T, class U>ostream &operator<<(ostream &os, const pair<T, U> &p) {return os << "(" << p.first << " " << p.second << ")";}template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template<class T>bool chmin(T &a, const T &b) {if (b < a) {a = b;return true;}return false;}using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;using vvi = vector<vi>;using vvll = vector<vll>;const ll MOD = 1e9 + 7;const int INF = INT_MAX / 2;const ll LINF = LLONG_MAX / 2;const ld eps = 1e-9;// edittemplate<typename E, typename O=E, typename F1=function<E(E, O)>, typename F2=function<E(E, E)>>struct Rerooting {struct Edge {int to;int rev;O w;};vector<vector<Edge>> graph;vector<vector<E>> dp;vector<vector<int>> vis;const int N;const E ie; // 要素の単位元const F1 f1;const F2 f2;Rerooting(int N, E ie, F1 f1, F2 f2) : graph(N), dp(N), vis(N), N(N), ie(ie), f1(f1), f2(f2) {}// 重みとかがない場合でもwに適当な値を入れておくことvoid add_edge(int u, int v, O w) {int su = graph[u].size();int sv = graph[v].size();graph[u].push_back({v, sv, w});graph[v].push_back({u, su, w});}// 根をrとしたときrのc番目の子の値を求めるE dfs_sub(int r, int c) {if (vis[r][c]) return dp[r][c];vis[r][c] = true;E &ret = dp[r][c];int u = graph[r][c].to;int su = graph[u].size();// TODO//葉に対する例外処理if (graph[u].size() == 1) {ret = 1;return ret;}bool win_exist = false;for (int i = 0; i < su; ++i) {int v = graph[u][i].to;if (v == r) continue;E sub_res = dfs_sub(u, i);// TODO// ret = f2(ret, f1(sub_res, graph[u][i].w));if (sub_res) {win_exist = true;}}// TODO 問題によってはここで処理が生じる// 例: TDPC-Vret = !win_exist;return ret;}void dfs_all(int u, int p = -1) {int su = graph[u].size();vector<E> es(su + 2, 0);vector<E> lce(su + 2, 0);vector<E> rce(su + 2, 0);for (int i = 0; i < su; ++i) {// TODOes[i + 1] = lce[i + 1] = rce[i + 1] = dfs_sub(u, i);}for (int i = 0; i <= su; ++i) {// lce[i + 1] = f2(lce[i], lce[i + 1]);lce[i + 1] = lce[i] || lce[i + 1];}for (int i = su + 1; i > 0; --i) {// rce[i - 1] = f2(rce[i], rce[i - 1]);rce[i - 1] = rce[i] || rce[i - 1];}for (int i = 0; i < su; ++i) {// vが根のときのuに関する値を求めるint v = graph[u][i].to;int rev = graph[u][i].rev;vis[v][rev] = true;// TODO// uが葉の場合の例外処理if (graph[u].size() == 1) {dp[v][rev] = 1;continue;}// TODO// dp[v][rev] = f2(lce[i], rce[i + 2]);dp[v][rev] = !(lce[i] || rce[i + 2]);}for (int i = 0; i < su; ++i) {int v = graph[u][i].to;if (v == p) continue;dfs_all(v, u);}}vector<E> build(int root = 0) {// dp, visの初期化for (int i = 0; i < N; ++i) {dp[i].resize(graph[i].size(), ie);vis[i].resize(graph[i].size(), false);}dfs_all(root, -1);vector<E> ret(N, ie);for (int u = 0; u < N; ++u) {int su = graph[u].size();bool win_exist = false;for (int i = 0; i < su; ++i) {// 部分問題を求めるE sub_res = dfs_sub(u, i);// TODO// 部分問題の結果に作用素を作用させる// E applied_res = f1(sub_res, graph[u][i].w);// TODO// ret[u] = f2(ret[u], applied_res);if (sub_res) win_exist = true;}ret[u] = !win_exist;}return ret;}};void solve() {int N;cin >> N;using E = int;using O = int;E ie = -1;using F1 = function<void(E, O)>;using F2 = function<void(E, E)>;F1 f1 = [](E e, O o) -> void {};F2 f2 = [](E e1, E e2) -> void {};Rerooting<E, O, F1, F2> rr(N + 1, ie, f1, f2);REP(i, N - 1) {int a, b;cin >> a >> b;rr.add_edge(a, b, 0);}auto res = rr.build(1);vector<int> win_node;FOR(i, 1, N + 1) {if (res[i]) {win_node.push_back(i);}}cout << win_node.size() << endl;for (auto node: win_node) {cout << node << endl;}}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(10);// std::ifstream in("input.txt");// std::cin.rdbuf(in.rdbuf());solve();return 0;}