Submission #1126539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126539		ntdaccode	Klasika (COCI20_klasika)	C++20	110 / 110	2845 ms	418736 KiB

klasika

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 3e6 + 10;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int n, q;
string st[N];
int a[N], b[N];

vector<ii> ke[N];

int num[N], tail[N], cnt = 0, d[N];
void dfs(int u)
{
  num[u] = ++ cnt;
  for(ii v : ke[u]) {
      d[v.first] = d[u] ^ v.second;
      dfs(v.first);
  }
  tail[u] = cnt;
}

int ch[2][M];

set<int> pos[M];

void add(int val,int p)
{
  int idx = 0;
  for(int i = 30; i >= 0; i--) {
    int k = (val >> i) & 1;
    if(!ch[k][idx]) ch[k][idx] = ++ cnt;
    idx = ch[k][idx];
    pos[idx].insert(p);
  }
}

bool check(int l, int r, int idx)
{
  if(pos[idx].size() == 0) return false;
  auto index = pos[idx].upper_bound(r);
  if(index == pos[idx].begin()) return false;
  index = prev(index);
  return l <= (*index) ;
}

int get(int l,int r,int val)
{
  int idx = 0, res = 0;
  for(int i = 30;i >= 0; i--) {
    int k = (val >> i) & 1;
    if(check(l,r,ch[1 - k][idx])) {
        res = res ^ (1 << i);
        idx = ch[1 - k][idx];
    }
    else idx = ch[k][idx];
  }
  return res;
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

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

  #define task ""
  if(fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> q;
  n = 1;
  for(int i = 1;i <= q; i++) {
    cin >> st[i] >> a[i] >> b[i];
    if(st[i] == "Add") {
        n++;
        ke[a[i]].pb({n,b[i]});
    }
  }
  dfs(1);
  cnt = 0;
  n = 1;
  add(d[1],1);
  for(int i = 1;i <= q; i++) {
      if(st[i] == "Add") {
        n++;
        add(d[n],num[n]);
      }
      else {
        cout << get(num[b[i]],tail[b[i]],d[a[i]]) << "\n";
      }
  }



}

Compilation message (stderr)

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

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