結果

問題 No.2800 Game on Tree Inverse
ユーザー ecotteaecottea
提出日時 2024-07-05 03:02:56
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 20,052 bytes
コンパイル時間 6,053 ms
コンパイル使用メモリ 306,876 KB
実行使用メモリ 77,980 KB
最終ジャッジ日時 2024-07-05 03:03:27
合計ジャッジ時間 30,049 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 29 WA * 35
権限があれば一括ダウンロードができます

ソースコード

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

#ifndef HIDDEN_IN_VS //
//
#define _CRT_SECURE_NO_WARNINGS
//
#include <bits/stdc++.h>
using namespace std;
//
using ll = long long; using ull = unsigned long long; // -2^63 2^63 = 9 * 10^18int -2^31 2^31 = 2 * 10^9
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
//
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
//
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
//
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 n-1
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s t
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s t
#define repe(v, a) for(const auto& v : (a)) // a
#define repea(v, a) for(auto& v : (a)) // a
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} //
#define EXIT(a) {cout << (a) << endl; exit(0);} //
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) //
//
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // true
    
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // true
    
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // mod
//
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif //
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
//using mint = modint1000000007;
using mint = modint998244353;
//using mint = static_modint<1234567891>;
//using mint = modint; // mint::set_mod(m);
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // Visual Studio
#include "local.hpp"
#else // gcc
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
template <size_t N> inline int lsb(const bitset<N>& b) { return b._Find_first(); }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_mat(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE MLE
#endif
//O(n + m)
/*
* (, ) n m
*
* n :
* m : n-1
* directed : false
* zero_indexed : 0-indexed false
*/
Graph read_Graph(int n, int m = -1, bool directed = false, bool zero_indexed = false) {
// verify : https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bi
Graph g(n);
if (m == -1) m = n - 1;
rep(j, m) {
int a, b;
cin >> a >> b;
if (!zero_indexed) { --a; --b; }
g[a].push_back(b);
if (!directed && a != b) g[b].push_back(a);
}
return g;
}
//O(?)
/*
* p
* nxt(p, nps) p nps
*/
template <class T>
map<T, int> calc_nimber(const T& p, function<void(const T&, vector<T>&)>& nxt) {
map<T, int> nim; //
function<int(const T&)> calc_nimber = [&](const T& p) {
if (nim.count(p)) return nim[p];
vector<T> nps;
nxt(p, nps);
vi next_nimbers;
repe(np, nps) {
next_nimbers.push_back(calc_nimber(np));
}
uniq(next_nimbers);
int i = 0;
while (i < sz(next_nimbers) && next_nimbers[i] == i) i++;
nim[p] = i;
return nim[p];
};
calc_nimber(p);
return nim;
/* nxt
using T = vi;
function<void(const T&, vector<T>&)> nxt = [&](const T& p, vector<T>& nps) {
};
*/
}
//O(n)
/*
* s∈[0..n) r g s -1
*/
vi parent_of_tree(const Graph& g, int r) {
int n = sz(g);
vi p(n);
function<void(int)> dfs = [&](int s) {
repe(t, g[s]) {
if (t == p[s]) continue;
p[t] = s;
dfs(t);
}
};
p[r] = -1;
dfs(r);
return p;
}
int get_nimber_naive(int n, Graph g) {
auto par = parent_of_tree(g, 0);
dump(par);
using T = vi;
function<void(const T&, vector<T>&)> nxt = [&](const T& p, vector<T>& nps) {
rep(s, n) {
if (p[s] == 1) continue;
auto np(p); int t = s;
while (t != -1) {
np[t] = 1;
t = par[t];
}
nps.push_back(np);
}
};
vi ini(n, 0);
auto gs = calc_nimber(ini, nxt);
return gs[ini];
}
// DPO(n)
/*
* r g s∈[0..n)
* s
*
* T leaf(int s) :
* s
*
* T add_edge(T x, int p, int s) :
* s x
* p'→s p' '
*
* void merge(T& x, T y, int s) :
* s' 2 x, y
* x y s' x
*
* void add_vertex(T& x, int s) :
* s' s' x
* s s x
*/
template <class T, T(*leaf)(int), T(*add_edge)(const T&, int, int), void(*merge)(T&, const T&, int), void(*add_vertex)(T&, int)>
vector<T> tree_getDP(const Graph& g, int r) {
// verify : https://atcoder.jp/contests/tdpc/tasks/tdpc_eel
int n = sz(g);
vector<T> dp(n);
// s p : s
function<void(int, int)> dfs = [&](int s, int p) {
// is_leaf : s
bool is_leaf = true;
repe(t, g[s]) {
if (t == p) continue;
// t
dfs(t, s);
// t s'→t s'
T sub = add_edge(dp[t], s, t);
// s'
if (is_leaf) dp[s] = move(sub);
else merge(dp[s], sub, s);
is_leaf = false;
}
// s
if (is_leaf) dp[s] = leaf(s);
// s
else add_vertex(dp[s], s);
};
dfs(r, -1);
return dp;
/*
struct T {
int v;
};
T leaf(int s) {
return T{ 1 };
}
T add_edge(const T& x, int p, int s) {
return x;
}
void merge(T& x, const T& y, int s) {
x.v += y.v;
}
void add_vertex(T& x, int s) {
x.v += 1;
}
vector<T> solve_by_tree_getDP(const Graph& g, int r) {
return tree_getDP<T, leaf, add_edge, merge, add_vertex>(g, r);
}
*/
};
//XOR O(log max(r, c))
/*
* {x∈[0..∞) | l ≦ (x XOR c) < r} O(log max(r, c))
*/
template <class T>
vector<pair<T, T>> XOR_interval_division(T l, T r, T c) {
// verify : https://yukicoder.me/problems/no/2505
chmax(l, T(0));
if (l >= r) return vector<pair<T, T>>();
int n = max(msb(r), msb(c));
vector<pair<T, T>> lrs; T val_l = 0, val_r = 0; bool eq = true;
repir(i, n, 0) {
T lb = getb(l, i), rb = getb(r, i), cb = getb(c, i);
if (eq) {
if (lb != rb) eq = false;
}
else {
if (!lb) {
T val_l2 = val_l + ((1 ^ cb) << i);
lrs.emplace_back(val_l2, val_l2 + (T(1) << i));
}
if (rb) {
T val_r2 = val_r + ((0 ^ cb) << i);
lrs.emplace_back(val_r2, val_r2 + (T(1) << i));
}
}
val_l += (lb ^ cb) << i;
val_r += (rb ^ cb) << i;
}
lrs.emplace_back(val_l, val_l + 1);
return lrs;
}
struct T {
int g;
int p;
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const T& x) {
os << '(' << x.g << ',' << x.p << ')';
return os;
}
#endif
};
T leaf(int s) {
return T{ 1, 0 };
}
T add_edge(const T& x, int p, int s) {
return T{ x.g + 1, x.g };
}
void merge(T& x, const T& y, int s) {
dump("x:", x, "y:", y);
vi imos((x.p ^ y.p) + 2);
imos[x.p ^ y.p]++;
imos[(x.p ^ y.p) + 1]--;
auto lrs1 = XOR_interval_division(0, x.g, y.p);
for (auto [l, r] : lrs1) {
if (sz(imos) <= r) imos.resize(r + 1);
imos[l]++;
imos[r]--;
}
auto lrs2 = XOR_interval_division(0, y.g, x.p);
for (auto [l, r] : lrs2) {
if (sz(imos) <= r) imos.resize(r + 1);
imos[l]++;
imos[r]--;
}
dump("imos:", imos);
rep(i, sz(imos) - 1) {
if (imos[i] == 0) {
x.g = i;
break;
}
imos[i + 1] += imos[i];
}
x.p ^= y.p;
}
void add_vertex(T& x, int s) {
;
}
vector<T> solve_by_tree_getDP(const Graph& g, int r) {
return tree_getDP<T, leaf, add_edge, merge, add_vertex>(g, r);
}
//O(?)
/*
* n
*/
Graph create_random_tree(int n) {
Graph g(n);
static mt19937_64 mt; static bool first_call = true;
if (first_call) {
mt = mt19937_64((int)time(NULL));
first_call = false;
}
uniform_int_distribution<int> rnd(0, n - 1);
dsu d(n);
while (d.size(0) < n) {
int u = rnd(mt), v = rnd(mt);
if (d.same(u, v)) continue;
g[u].emplace_back(v);
g[v].emplace_back(u);
d.merge(u, v);
}
return g;
}
//O(n + m)
/*
*
*
* directed : false
* zero_indexed : 0-indexed false
*/
void write_Graph(const Graph& g, bool directed = false, bool zero_indexed = false) {
// verify : https://www.codechef.com/problems/B_BRANCH
int n = sz(g);
// m :
int m = 0;
rep(s, n) m += sz(g[s]);
if (!directed) m /= 2;
cout << n << " " << m << endl;
rep(s, n) repe(t, g[s]) {
if (!directed && s > t) continue;
int u = s + (!zero_indexed), v = t + (!zero_indexed);
cout << u << " " << v << " " << endl;
}
}
//
/*
* Interval_set<T>(T L = -INFL, T R = INFL) : O(1)
* [L..R)
*
* int size() : O(1)
*
*
* pTT get(T x) : O(log n)
* x [l..r) {-1, -1}
*
* pTT get_right(T x) : O(log n)
* x < l [l..r) {R+1, R+1}
*
* pTT get_left(T x) : O(log n)
* r ≦ x [l..r) {L-1, L-1}
*
* insert(T l, T r) : O(log n)
* [l..r)
*
* erase(T l, T r) : O(log n)
* [l..r)
*
* vector<pTT> get_all_intervals() : O(n)
* [l..r)
*/
template <class T>
class Interval_set {
// L, R : [L..R)
T L, R;
// l_to_r[l] : l [l..r) r
map<T, T> l_to_r;
public:
// [L..R)
Interval_set(T L = -(T)INFL, T R = (T)INFL) : L(L), R(R) {
// verify : https://yukicoder.me/problems/no/2292
l_to_r[L - 1] = L - 1;
l_to_r[R + 1] = R + 1; //
}
//
int size() const {
return sz(l_to_r);
}
// x [l..r) {-1, -1}
pair<T, T> get(T x) const {
// verify : https://yukicoder.me/problems/no/2292
Assert(L <= x && x < R);
auto it = prev(l_to_r.upper_bound(x));
return it->second <= x ? make_pair(T(-1), T(-1)) : pair<T, T>(*it);
}
// x < l [l..r) {R+1, R+1}
pair<T, T> get_right(T x) const {
// verify : https://atcoder.jp/contests/code-festival-2015-qualb/tasks/codefestival_2015_qualB_d
Assert(L <= x && x < R);
auto it = l_to_r.upper_bound(x);
return *it;
}
// r ≦ x [l..r) {L-1, L-1}
pair<T, T> get_left(T x) const {
Assert(L <= x && x < R);
auto it = prev(l_to_r.lower_bound(x));
return it->second <= x ? *it : *prev(it);
}
// [l..r)
void insert(T l, T r) {
// verify : https://yukicoder.me/problems/no/2292
chmax(l, L); chmin(r, R);
if (l >= r) return;
auto it = l_to_r.lower_bound(l);
// [l..r)
auto pit = prev(it);
if (l <= pit->second) {
//if (l < pit->second) { //
l = pit->first;
it = pit;
}
while (true) {
if (r < it->first) break;
//if (r <= it->first) break; //
// [l..r)
if (r <= it->second) {
r = it->second;
l_to_r.erase(it);
break;
}
it = l_to_r.erase(it);
}
l_to_r[l] = r;
}
// [l..r)
void erase(T l, T r) {
// verify : https://yukicoder.me/problems/no/2292
chmax(l, L); chmin(r, R);
if (l >= r) return;
auto it = l_to_r.lower_bound(l);
// [l..r)
auto pit = prev(it);
if (l < pit->second) {
// [l..r)
if (r < pit->second) l_to_r[r] = pit->second;
pit->second = l;
}
while (true) {
if (r <= it->first) break;
// [l..r)
if (r < it->second) {
T nr = it->second;
l_to_r.erase(it);
l_to_r[r] = nr;
break;
}
it = l_to_r.erase(it);
}
}
// [l..r)
vector<pair<T, T>> get_all_intervals() const {
// verify : https://atcoder.jp/contests/abc254/tasks/abc254_g
vector<pair<T, T>> res;
res.reserve(sz(l_to_r) - 2);
repe(lr, l_to_r) {
if (lr.first == L - 1 || lr.first == R + 1) continue;
res.push_back(lr);
}
return res;
}
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const Interval_set& IS) {
repe(p, IS.l_to_r) {
if (p.first == IS.L - 1 || p.first == IS.R + 1) continue;
os << "[" << p.first << "," << p.second << ") ";
}
return os;
}
#endif
};
struct T2 {
Interval_set<int> s;
int r;
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const T2& x) {
os << '(' << x.s << ',' << x.r << ')';
return os;
}
#endif
};
T2 leaf2(int s) {
T2 x;
x.s.insert(0, 1);
x.r = 0;
return x;
}
T2 add_edge2(const T2& x, int p, int s) {
auto [l, r] = x.s.get(0);
T2 z(x);
z.s.insert(r, r + 1);
z.r = r;
return z;
}
void merge2(T2& x, const T2& y, int s) {
dump("x:", x, "y:", y);
T2 z;
auto tmp = x.s.get_all_intervals();
for (auto& [l, r] : tmp) {
for (auto& [l2, r2] : XOR_interval_division(l, r, y.r)) {
z.s.insert(l2, r2);
}
}
auto tmp2 = y.s.get_all_intervals();
for (auto& [l, r] : tmp2) {
for (auto& [l2, r2] : XOR_interval_division(l, r, x.r)) {
z.s.insert(l2, r2);
}
}
z.r = x.r ^ y.r;
x = move(z);
}
void add_vertex2(T2& x, int s) {
;
}
vector<T2> solve_by_tree_getDP2(const Graph& g, int r) {
return tree_getDP<T2, leaf2, add_edge2, merge2, add_vertex2>(g, r);
}
void bug_find() {
#ifdef _MSC_VER
//
mute_dump = true;
mt19937_64 mt;
mt.seed((int)time(NULL));
uniform_int_distribution<ll> rnd(0LL, 1LL << 60);
rep(hoge, 1000) {
int n = rnd(mt) % 10 + 2;
auto g = create_random_tree(n);
auto res_naive = get_nimber_naive(n, g);
auto dp = solve_by_tree_getDP2(g, 0);
auto [l, r] = dp[0].s.get(0);
auto res_solve = r;
if (res_naive != res_solve) {
cout << "----------error!----------" << endl;
cout << "input:" << endl;
write_Graph(g, 0, 1);
cout << "results:" << endl;
cout << res_naive << endl;
cout << res_solve << endl;
cout << "--------------------------" << endl;
}
}
mute_dump = false;
exit(0);
#endif
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// bug_find();
int n;
cin >> n;
auto g = read_Graph(n);
dump(get_nimber_naive(n, g)); dump("-----");
auto dp = solve_by_tree_getDP2(g, 0);
dump(dp);
int x = dp[0].s.get(0).second;
vi res;
function<void(int, int)> dfs = [&](int s, int p) {
auto tmp = dp[s].s.get(0).second;
x ^= tmp;
x ^= dp[s].r;
dump("s:", s, "x:", x);
if (x == 0) {
res.push_back(s);
}
repe(t, g[s]) {
if (t == p) continue;
dfs(t, s);
}
x ^= tmp;
x ^= dp[s].r;
};
dfs(0, -1);
cout << "Alice" << endl;
cout << sz(res) << endl;
int K = sz(res);
rep(k, K) cout << res[k] + 1 << " \n"[k == K - 1];
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0