2016-2017 ACM-ICPC Asia-Bangkok Regional Contest F - Dictionary Game

問題ページ
trie木を構成すると D - Game on Tree に帰着できる．追加するクエリが存在するが，文字列追加でgrundy数が変更される頂点の数は高々40個なのでその部分だけgrundy数を再計算すればよい．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int itr = 1;  
int ch[100010*40][26], grundy[100010*40], par[100010*40];  
  
int add(string s) {  
    int now = 0;  
    REP(j, s.size()) {  
        int nxt = s[j]-'a';  
        if(ch[now][nxt] == 0) {  
            ch[now][nxt] = itr;  
            par[itr] = now;  
            itr++;  
        }  
        now = ch[now][nxt];  
    }  
    return now;  
}  
  
void dfs(int v) {  
    REP(i, 26) if(ch[v][i]) dfs(ch[v][i]);  
    grundy[v] = 0;  
    REP(i, 26) if(ch[v][i]) grundy[v] ^= grundy[ch[v][i]]+1;  
}  
  
void solve(ll test) {  
    ll n;  
    cin >> n;  
    REP(i, n) {  
        string s;  
        cin >> s;  
        add(s);  
    }  
    dfs(0);  
  
    ll q;  
    cin >> q;  
    cout << "Case " << test+1 << ":\n";  
    REP(i, q) {  
        string s;  
        cin >> s;  
      
        int now = add(s);  
        while(1) {  
            grundy[now] = 0;  
            REP(i, 26) if(ch[now][i]) grundy[now] ^= grundy[ch[now][i]]+1;  
            if(now == 0) break;  
            now = par[now];  
        }  
  
        cout << (grundy[0]==0 ? 2 : 1) << "\n";  
    }  
}  
  
int main(void) {  
    ll t;  
    cin >> t;  
    REP(i, t) {  
        solve(i);  
        REP(j, itr) {  
            grundy[j] = 0;  
            REP(k, 26) ch[j][k] = 0;  
        }  
        itr = 1;  
    }   
  
    return 0;  
}  
``