結果

問題 No.2800 Game on Tree Inverse
ユーザー noya2noya2
提出日時 2024-06-09 02:15:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 645 ms / 4,000 ms
コード長 5,161 bytes
コンパイル時間 2,896 ms
コンパイル使用メモリ 260,256 KB
実行使用メモリ 216,480 KB
最終ジャッジ日時 2024-06-09 02:37:31
合計ジャッジ時間 23,638 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,376 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 376 ms
77,824 KB
testcase_04 AC 410 ms
127,744 KB
testcase_05 AC 454 ms
156,416 KB
testcase_06 AC 458 ms
171,900 KB
testcase_07 AC 496 ms
198,344 KB
testcase_08 AC 504 ms
214,440 KB
testcase_09 AC 645 ms
216,480 KB
testcase_10 AC 464 ms
120,996 KB
testcase_11 AC 517 ms
164,224 KB
testcase_12 AC 500 ms
147,200 KB
testcase_13 AC 474 ms
146,048 KB
testcase_14 AC 482 ms
157,568 KB
testcase_15 AC 516 ms
156,032 KB
testcase_16 AC 475 ms
158,544 KB
testcase_17 AC 483 ms
126,464 KB
testcase_18 AC 448 ms
131,936 KB
testcase_19 AC 507 ms
143,616 KB
testcase_20 AC 479 ms
140,068 KB
testcase_21 AC 470 ms
147,328 KB
testcase_22 AC 526 ms
158,128 KB
testcase_23 AC 482 ms
139,772 KB
testcase_24 AC 402 ms
117,248 KB
testcase_25 AC 423 ms
128,176 KB
testcase_26 AC 422 ms
145,024 KB
testcase_27 AC 518 ms
152,180 KB
testcase_28 AC 519 ms
172,156 KB
testcase_29 AC 421 ms
100,736 KB
testcase_30 AC 422 ms
124,416 KB
testcase_31 AC 553 ms
168,972 KB
testcase_32 AC 441 ms
129,792 KB
testcase_33 AC 457 ms
147,128 KB
testcase_34 AC 574 ms
191,464 KB
testcase_35 AC 477 ms
143,648 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 1 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 1 ms
5,376 KB
testcase_47 AC 5 ms
5,376 KB
testcase_48 AC 3 ms
5,376 KB
testcase_49 AC 17 ms
8,104 KB
testcase_50 AC 10 ms
6,272 KB
testcase_51 AC 243 ms
68,352 KB
testcase_52 AC 22 ms
9,344 KB
testcase_53 AC 50 ms
18,176 KB
testcase_54 AC 236 ms
67,328 KB
testcase_55 AC 402 ms
105,300 KB
testcase_56 AC 307 ms
85,504 KB
testcase_57 AC 428 ms
115,964 KB
testcase_58 AC 147 ms
45,952 KB
testcase_59 AC 198 ms
58,624 KB
testcase_60 AC 133 ms
41,856 KB
testcase_61 AC 95 ms
31,232 KB
testcase_62 AC 145 ms
43,520 KB
testcase_63 AC 168 ms
48,640 KB
testcase_64 AC 61 ms
21,248 KB
testcase_65 AC 58 ms
20,992 KB
権限があれば一括ダウンロードができます

ソースコード

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