結果

問題 No.2800 Game on Tree Inverse
ユーザー noya2
提出日時 2024-06-09 02:15:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 779 ms / 4,000 ms
コード長 5,161 bytes
コンパイル時間 3,813 ms
コンパイル使用メモリ 258,756 KB
実行使用メモリ 216,460 KB
最終ジャッジ日時 2024-12-29 01:25:43
合計ジャッジ時間 34,056 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T, int LOG>
struct binary_trie {
    struct node {
        node *p;
        array<node*,2> ch;
        int leaf, sz;
        node () : p(nullptr), ch({nullptr,nullptr}), leaf(0), sz(0) {}
    };
    binary_trie () : lazy(0) {}
    int size(node *v){
        if (v == nullptr) return 0;
        return v->sz;
    }
    int size(){
        return size(root);
    }
    void insert(T x){
        x ^= lazy;
        node *v = root;
        for (int i = LOG-1; i >= 0; i--){
            int j = x >> i & 1;
            if (v->ch[j] == nullptr){
                v->ch[j] = new node();
                v->ch[j]->p = v;
            }
            v = v->ch[j];
        }
        v->leaf = 1;
        update(v);
        for (int i = 0; i < LOG; i++){
            v = v->p;
            update(v);
        }
    }
    void erase(T x){
        x ^= lazy;
        node *v = root;
        for (int i = LOG-1; i >= 0; i--){
            int j = x >> i & 1;
            if (v->ch[j] == nullptr) return ;
            v = v->ch[j];
        }
        v->leaf = 0;
        update(v);
        for (int i = 0; i < LOG; i++){
            node *p = v->p;
            if (size(v) == 0){
                (v == p->ch[0] ? p->ch[0] : p->ch[1]) = nullptr;
                delete v;
            }
            v = p;
            update(v);
        }
    }
    int count(T x){
        node *v = root;
        int res = 0;
        for (int i = LOG-1; i >= 0; i--){
            int j = lazy >> i & 1;
            if (x >> i & 1){
                res += size(v->ch[j]);
                v = v->ch[j^1];
            }
            else {
                v = v->ch[j];
            }
            if (v == nullptr) break;
        }
        return res;
    }
    T get(int k){
        if (k < 0 || k >= size()) return -1;
        node *v = root;
        T ans = 0;
        for (int i = LOG-1; i >= 0; i--){
            int j = lazy >> i & 1;
            if (k < size(v->ch[j])){
                v = v->ch[j];
            }
            else {
                k -= size(v->ch[j]);
                v = v->ch[j^1];
                ans |= T(1) << i;
            }
        }
        return ans;
    }
    T mex(){
        if ((T)size() == (T(1)<<LOG)) return T(1)<<LOG;
        node *v = root;
        T ans = 0;
        for (int i = LOG-1; i >= 0; i--){
            int j = lazy >> i & 1;
            if ((T)size(v->ch[j]) < (T(1)<<i)){
                v = v->ch[j];
            }
            else {
                v = v->ch[j^1];
                ans |= T(1) << i;
            }
            if (v == nullptr) break;
        }
        return ans;
    }
    T xor_all(T x){ return lazy ^= x; }
    vector<T> enumerate(){
        vector<T> ans; ans.reserve(size());
        auto dfs = [&](auto sfs, int i, T x, node *v) -> void {
            if (i == -1){
                ans.emplace_back(x^lazy);
                return ;
            }
            if (v->ch[0] != nullptr){
                sfs(sfs,i-1,x,v->ch[0]);
            }
            if (v->ch[1] != nullptr){
                sfs(sfs,i-1,x|(T(1)<<i),v->ch[1]);
            }
        };
        dfs(dfs,LOG-1,0,root);
        return ans;
    }
  private:
    T lazy;
    node *root = new node();
    void update(node *v){
        v->sz = v->leaf + size(v->ch[0]) + size(v->ch[1]);
    }
};

int main(){
    int n; cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v; u--, v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<binary_trie<int,20>> bts(n);
    vector<int> dp(n);
    auto dfs = [&](auto sfs, int v, int f) -> int {
        vector<int> ids;
        for (auto u : g[v]){
            if (u == f) continue;
            ids.emplace_back(sfs(sfs,u,v));
        }
        int ma = -1, id = v;
        int gr = 0;
        for (int i : ids){
            if (chmax(ma,bts[i].size())){
                id = i;
            }
            gr ^= bts[i].mex();
        }
        for (int i : ids){
            bts[i].xor_all(bts[i].mex()^gr);
        }
        for (int i : ids){
            if (i == id) continue;
            for (int x : bts[i].enumerate()){
                bts[id].insert(x);
            }
        }
        bts[id].insert(bts[id].mex()); // bts[id].mex() == gr
        dp[v] = bts[id].mex();
        return id;
    };
    dfs(dfs,0,-1);
    vector<int> vec;
    auto win = [&](auto sfs, int v, int f, int x) -> void {
        int c = 0;
        for (int u : g[v]){
            if (u == f) continue;
            c ^= dp[u];
        }
        if (c == x){
            vec.emplace_back(v);
        }
        for (int u : g[v]){
            if (u == f) continue;
            sfs(sfs,u,v,x^c^dp[u]);
        }
    };
    win(win,0,-1,0);
    sort(all(vec));
    cout << "Alice" << endl;
    cout << vec.size() << endl;
    for (int x : vec){
        if (x != vec[0]){
            cout << ' ';
        }
        cout << x+1;
    }
    cout << endl;
}
0