Submission #1247973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247973		SoMotThanhXuan	Klasika (COCI20_klasika)	C++20	110 / 110	4669 ms	444724 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define Bit(x, i) ((x >> (i)) & 1)
#define Mask(i) (1 << (i))
#define Cnt(x) __builtin_popcount(x)
#define Cntll(x) __builtin_popcountll(x)
#define Ctz(x) __builtin_ctz(x) // so luong so 0 tinh tu ben phai
#define Ctzll(x) __builtin_ctzll(x)
#define Clz(x) __builtin_clz(x) // so luong so 0 tinh tu ben trai
#define Clzll(x) __builtin_clzll(x)
inline bool maximize(int &u, int v){
    return v > u ? u = v, true : false;
}
inline bool minimize(int &u, int v){
    return v < u ? u = v, true : false;
}
inline bool maximizell(long long &u, long long v){
    return v > u ? u = v, true : false;
}
inline bool minimizell(long long &u, long long v){
    return v < u ? u = v, true : false;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
//inline void add(int &u, int v){
//    u += v;
//    if(u >= mod) u -= mod;
//}
//inline void sub(int &u, int v){
//    u -= v;
//    if(u < 0) u += mod;
//}
const int maxN = 2e5 + 5;
const int inf = 1e9;
const long long infll = 1e18;
int q, n;
int type[maxN];
int X[maxN], Y[maxN];
vector<pair<int, int>> child[maxN];
vector<pair<int, int>> query[maxN];
int hv[maxN], sz[maxN], sum[maxN], d[maxN];
int in[maxN], out[maxN], id[maxN], timeDfs;
void dfs(int u = 1){
    sz[u] = 1;
    in[u] = ++timeDfs;
    id[timeDfs] = u;
    for(auto[v, w] : child[u]){
        sum[v] = sum[u] ^ w;
        d[v] = d[u] + 1;
        dfs(v);
        sz[u] += sz[v];
        if(sz[v] > sz[hv[u]])hv[u] = v;
    }
    out[u] = timeDfs;
}
struct Trie{
    Trie *child[2], *par;
    set<int> node;
    Trie(){
        par = nullptr;
        FOR(i, 0, 1)child[i] = nullptr;
    }
}*root;
void add(int u, int val){
    Trie *p = root;
    for(int i = 30; i >= 0; --i){
        int cur = Bit(val, i);
        Trie *pre = p;
        if(p -> child[cur] == nullptr) p -> child[cur] = new Trie();
        p = p -> child[cur];
        p -> node.insert(u);
        p -> par = pre;
    }
}
void del(int u, int val){
    Trie *p = root;
    for(int i = 30; i >= 0; --i){
        int cur = Bit(val, i);
        Trie *pre = p;
        p = p -> child[cur];
        p -> node.erase(u);
    }
    for(int i = 0; i <= 30; ++i){
        p = p -> par;
        int cur = Bit(val, i);
        if(p -> child[cur] -> node.empty()){
            delete p -> child[cur];
            p -> child[cur] = nullptr;
        }
    }
}
int get(int val, int maxNode){
    Trie *p = root;
    int answer = 0;
    for(int i = 30; i >= 0; --i){
        int cur = Bit(val, i);
        if(p -> child[cur ^ 1] != nullptr){
            if(* p -> child[cur ^ 1] -> node.begin() <= maxNode){
                answer |= Mask(i);
                p = p -> child[cur ^ 1];
            }else{
                p = p -> child[cur];
            }
        }else{
            p = p -> child[cur];
        }
    }
    return answer;
}
int res[maxN];
void sack(int u = 1){
    for(auto[v, w] : child[u]){
        if(v != hv[u]){
            sack(v);
            FOR(i, in[v], out[v]) del(id[i], sum[id[i]]);
        }
    }
    if(hv[u]) sack(hv[u]);
    add(u, sum[u]);
    for(auto[v, w] : child[u]){
        if(v != hv[u]){
            FOR(i, in[v], out[v]) add(id[i], sum[id[i]]);
        }
    }
    for(auto[id, maxNode] : query[u]){
        int a = X[id];
        res[id] = get(sum[a], maxNode);
    }
}
void process(){
    cin >> q;
    n = 1;
    root = new Trie();
    FOR(i, 1, q){
        string s;
        cin >> s >> X[i] >> Y[i];
        if(s[0] == 'A')type[i] = 1;
        else type[i] = 2;
        if(type[i] == 1){
            ++n;
            child[X[i]].emplace_back(n, Y[i]);
        }
        else{
            query[Y[i]].emplace_back(i, n);
        }
    }
    dfs();
    sack();

    FOR(i, 1, q){
        if(type[i] == 2){
            cout << res[i] << '\n';
        }
    }
}
#define LOVE ""
int main(){
    if(fopen(LOVE".inp", "r")){
        freopen(LOVE".inp", "r", stdin);
        freopen(LOVE".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--)
        process();
//    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(LOVE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(LOVE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44