Submission #1042362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042362		khanhtb	Klasika (COCI20_klasika)	C++14	110 / 110	1614 ms	408832 KiB

klasika

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll int
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
const ll inf = 1e18;
const ll base = 26;
const ll blocksz = 320;
const ll N = 2e5+8;
const ll lim = 3e6+8;
// Road to Candidate Master: 268pts left
// Target: Top 1 CHD
// Ultimate Target: VOI 202k (k = ?????)
struct node{
    ll child[2];
    node(){
        child[0] = child[1] = 0;
    }
} trie[lim];
set<ll> idx[lim];
ll nownode = 0;
void add(ll x, ll id){
    ll u = 0;
    for(ll i = 29; i >= 0; i--){
        bool k = (x>>i&1);
        if(!trie[u].child[k]){
            trie[u].child[k] = ++nownode;
            trie[nownode] = node();
        }
        u = trie[u].child[k];
        idx[u].insert(id);
    }
}
bool ok(ll u, ll l, ll r){
    auto p = idx[u].lower_bound(l);
    return (p != idx[u].end() && (*p) <= r);
}
ll query(ll x, ll l, ll r){
    ll u = 0,ans = 0;
    for(ll i = 29; i >= 0; i--){
        bool k = (x>>i&1);
        if(trie[u].child[!k] && ok(trie[u].child[!k],l,r)){
            ans |= (1<<i);
            u = trie[u].child[!k];
        }
        else u = trie[u].child[k];
    }
    return ans;
}
vpll g[N];
ll h[N],tin[N],tout[N],tdfs;
void dfs(ll u){
    tin[u] = ++tdfs;
    for(auto [v,w]:g[u]){
        if(!tin[v]) dfs(v);
    }
    tout[u] = tdfs;
}
struct info{
    char s;
    ll x,y;
};
vector<info> qr;
ll q;
void solve(){
    trie[0] = node();
    cin >> q;
    ll now = 1;
    while(q--){
        string s;
        ll x,y;
        cin >> s >> x >> y;
        qr.pb({s[0],x,y});
        if(s[0] == 'A'){
            now++;
            g[x].pb({now,y});
            h[now] = (h[x]^y);
        }
    }
    dfs(1);
    add(h[1],tin[1]);
    ll nnode = 1;
    for(auto [s,x,y]:qr){
        if(s == 'A'){
            nnode++;
            add(h[nnode],tin[nnode]);
        }
        else{
            ll ans = query(h[x],tin[y],tout[y]);
            cout << ans << '\n';
        }
    }
}
signed main(){
    if(fopen("test.inp","r")){
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    for(int tt = 1; tt <= T; ++tt){
        solve();
        cout << '\n';   
    }  
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
}

Compilation message (stderr)

klasika.cpp:19:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const ll inf = 1e18;
      |                ^~~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [v,w]:g[u]){
      |              ^
klasika.cpp: In function 'void solve()':
klasika.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [s,x,y]:qr){
      |              ^
klasika.cpp: In function 'int main()':
klasika.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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