Submission #1132018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132018		Sam_arvandi	Klasika (COCI20_klasika)	C++17	0 / 110	38 ms	29504 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, mn2 = (1<<18) + 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;
     };

     vector<Node> node;

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

     int maxi(int id, int x, int p)
     {
	  if (p == -1) return 0;
	  if (x&(1<<p))
	  {
	       if (node[id].lc == 0) return maxi(node[id].rc, x, p-1);
	       return maxi(node[id].lc, x, p-1) + (1<<p);
	  }
	  else
	  {
	       if (node[id].rc == 0) return maxi(node[id].lc, x, p-1);
	       return maxi(node[id].rc, x, p-1) + (1<<p);
	  }
     }


};


struct Seg_tree
{
     struct Node
     {
	  Trie tr;
     }node[mn2*2];

     void update(int id, int L, int R, int ind, int x)
     {
	  //cout << id << endl;
	  node[id].tr.add(1, x, 30);
	  //cout << id << endl;
	  if (L+1 == R) return;
	  int mid = (L+R)/2;
	  if (ind >= mid) update(id*2 + 1, mid, R, ind, x);
	  else update(id*2, L, mid, ind, x);
	  return;
     }

     int get(int id, int L, int R, int l, int r, int x)
     {
	  if (L == l and R == r)
	  {
	       return node[id].tr.maxi(1, x, 30);
	  }
	  int mid =(L+R)/2;
	  if (l >= mid) return get(id* 2+ 1, mid, R, l, r, x);
	  else if ( r<= mid) return get(id*2, L, mid, l, r, x);
	  else
	  {
	       return max(get(id*2, L, mid, l, mid, x), get(id*2 + 1, mid, R, mid, r, x));
	  }
     }

}seg;


int main()
{
     IOS;
     cin.tie(0);
     cout.tie(0);
     int u, v, q, n= 1, n2 = 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;
	  }
     }
     while (n2 < n) n2 *= 2;
     dfs(1);
     FOR(i, 1, n2)
     {
	  seg.node[i].tr.node.push_back({0, 0});
	  seg.node[i].tr.node.push_back({0, 0});
     }
     seg.update(1, 1, n+1, 1, 0);
     FOR(i, 1, q)
     {
	  if (qu[i].first)
	  {
	       cout << seg.get(1, 1, n+1, st[qu[i].second.second], ft[qu[i].second.second]+1, w[qu[i].second.first]) << "\n";
	  }
	  else seg.update(1, 1, n+1, st[qu[i].second.second], w[qu[i].second.second]);
     }





     return 0;
}

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