Submission #1319064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319064		lmduc270410	Klasika (COCI20_klasika)	C++20	110 / 110	1732 ms	469432 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

const int LG = 30;

struct node{
  int ch[2];
  set<int> st;
  node(){
    ch[0] = ch[1] = -1;
    st.clear();
  }
};

node null;

vector<node> tr;
int cur = 0;

int add(){
  tr.push_back(null);
  return ++cur;
}

void add_num(int num, int tin){
  int pos = 0;
  for(int i = LG; i >= 0; i--){
    int c = num >> i & 1;
    if(tr[pos].ch[c] == -1){
      tr[pos].ch[c] = add();
    }
    pos = tr[pos].ch[c];
    tr[pos].st.insert(tin);
  }
}

int calc(int num, int l, int r){
  // if(tr[0].st.empty()) return 0;
  int pos = 0, res = 0;
  for(int i = LG; i >= 0; i--){
    int c = (num >> i & 1) ^ 1;
    if(tr[pos].ch[c] == -1) c ^= 1;
    else{
      int npos = tr[pos].ch[c];
      auto j = tr[npos].st.lower_bound(l);
      if(j == tr[npos].st.end() || *j > r) c ^= 1;
    }
    res |= (c << i);
    pos = tr[pos].ch[c];
    if(pos == -1) return 0;
  }
  return (res ^ num);
}

int q;
struct query{
  bool t; int x, y;
} qu[N];

vector<int> adj[N];
int n, val[N], ans[N];
int tin[N], tout[N], timer = 0, tour[N];

void dfs(int u){
  tin[u] = ++timer;
  tour[timer] = u;
  for(int v : adj[u]){
    dfs(v);
  }
  tout[u] = timer;
}

void solve(){
  
  cin>>q;
  n = 1; val[1] = 0;
  for(int i = 1; i <= q; i++){
    string s;
    cin>>s>>qu[i].x>>qu[i].y;
    qu[i].t = (s[0] == 'A');
    if(qu[i].t){
      adj[qu[i].x].push_back(++n);
      val[n] = val[qu[i].x] ^ qu[i].y;
      qu[i].y = n;
    }
  }

  null.ch[0] = null.ch[1] = -1; null.st.clear();
  tr.push_back(null);
  dfs(1);
  add_num(val[1], tin[1]);

  memset(ans, -1, sizeof(ans));
  for(int i = 1; i <= q; i++){
    if(qu[i].t){
      add_num(val[qu[i].y], tin[qu[i].y]);
    }
    else{
      cout<<calc(val[qu[i].x], tin[qu[i].y], tout[qu[i].y])<<'\n';
    }
  }
  for(int i = 1; i <= q; ++i){
      if(ans[i] != -1) cout<<ans[i]<<'\n';
  }
}

signed main(){
  
  if(fopen(".inp", "r")){
    freopen(".inp", "r", stdin);
    freopen(".out", "w", stdout);
  }

  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int tc = 1;
  // cin>>tc;
  while(tc--) solve();
}

Compilation message (stderr)

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

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