Submission #1132029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132029		Sam_arvandi	Klasika (COCI20_klasika)	C++17	110 / 110	2773 ms	478716 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair
#define IOS ios_base :: sync_with_stdio(false)
#define FOR(i, a, b) for(int i = a; i<= b; i++)
#define ROF(i, b, a) for(int i = b; i>= a; i--)

const int mn = 2e5 + 5;

int w[mn], st[mn], ft[mn];
pair<bool , pii>  qu[mn];
bool mark[mn];
vector<int> a[mn];

int tmp = 0;
void dfs(int u)
{
     tmp++;
     mark[u] = 1;
     st[u] = tmp;
     for(auto v: a[u])
     {
	  if (!mark[v]) dfs(v);
     }
     ft[u] = tmp;
     return;
}


struct Trie
{
     int P = 1;
     struct Node
     {
	  int lc = 0, rc = 0;
	  set<int> s;
     }temp;

     vector<Node> node;
     void add(int id, int ind , int x, int p)
     {
	  node[id].s.insert(ind);
	  if (p == -1) return;
	  if (x&(1<<p))
	  {
	       if (node[id].rc == 0)
	       {
		    P++;
		    node[id].rc = P;
		    node.push_back(temp);
	       }
	       add(node[id].rc, ind, x, p-1);
	  }
	  else
	  {
	       if (node[id].lc == 0)
	       {
		    P++;
		    node[id].lc = P;
		    node.push_back(temp);
	       }
	       add(node[id].lc, ind, x, p-1);
	  }
	  return;
     }

     int get(int id, int l, int r, int x, int p)
     {
	  if (p == -1) return 0;
	  bool bl = 0, br = 0;
	  auto it = node[node[id].lc].s.lower_bound(l);
	  if (it != node[node[id].lc].s.end() and (*it) <= r) bl = 1;
	  auto it2 = node[node[id].rc].s.lower_bound(l);
	  if (it2 != node[node[id].rc].s.end() and (*it2) <= r) br = 1;
	  
	  if (x&(1<<p))
	  {
	       if (bl) return get(node[id].lc, l, r, x, p-1) + (1<<p);
	       return get(node[id].rc, l, r, x, p-1);
	  }
	  else
	  {
	       if (br) return get(node[id].rc, l, r, x, p-1) + (1<<p);
	       return get(node[id].lc, l, r, x, p-1);
	  }
     }

}tr;




int main()
{
     IOS;
     cin.tie(0);
     cout.tie(0);
     int u, v, q, n= 1;
     cin >> q;
     FOR(i, 1, q)
     {
	  string type;
	  cin >> type >> u >> v;
	  if (type[0] == 'Q')
	  {
	       qu[i] = mp(1, mp(u, v));
	  }
	  else
	  {
	       n++;
	       qu[i] = mp(0, mp(u, n));
	       a[u].push_back(n);
	       a[n].push_back(u);
	       w[n] = w[u]^v;
	  }
     }
     dfs(1);
     tr.node.push_back(tr.temp);
     tr.node.push_back(tr.temp);
     tr.add(1, 1, 0, 30);

     FOR(i, 1, q)
     {
	  if (qu[i].first)
	  {
	       cout << tr.get(1, st[qu[i].second.second], ft[qu[i].second.second], w[qu[i].second.first], 30) << "\n";
	  }
	  else tr.add(1, st[qu[i].second.second], w[qu[i].second.second], 30);
     }





     return 0;
}

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