oj.uz

Submission #1017226

# Submission time Handle Problem Language Result Execution time Memory
1017226 2024-07-09T06:47:33 Z vjudge1 Klasika (COCI20_klasika) C++17
11 / 110
 600 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;

struct node
{
  node * ch[2];
  node()
  {
    ch[0] = ch[1] = NULL;
  }
  
  void insert(int x, int b = 30)
  {
    if(b == -1) return;
    bool bit = (1 << b) & x;
    if(ch[bit] == NULL)
      ch[bit] = new node();
    ch[bit] -> insert(x, b - 1);
  }

  int query(int x, int b = 30)
  {
    if(b == -1) return 0;
    bool bit = (1 << b) & x;
    if(ch[!bit] != NULL)
      return (1 << b) + ch[!bit] -> query(x, b - 1);
    return ch[bit] -> query(x, b - 1);
  }
};
const int N = 2005;
node *Tries[N];
int path[N], par[N];

int main()
{
  int q;
  cin >> q;
  int cnt = 1;
  Tries[1] = new node();
  Tries[1] -> insert(path[1]);
  for(int i = 0; i < q; i++)
    {
      string cmd;
      int a, b;
      cin >> cmd >> a >> b;
      if(cmd == "Query")
	{
	  cout << Tries[b] -> query(path[a]) << endl;
	}
      else
	{
	  cnt++;
	  path[cnt] = path[a] ^ b;
	  if(q > 2000)
	    Tries[1] -> insert(path[cnt]);
	  else
	    {
	      par[cnt] = a;
	      Tries[cnt] = new node();
	      int cur = cnt;
	      while(cur > 0)
		{
		  Tries[cur] -> insert(path[cnt]);
		  cur = par[cur];
		}
	    }
	}
    }
  
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 5 ms 6236 KB Output is correct
4 Correct 9 ms 9448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 2136 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 5 ms 6236 KB Output is correct
4 Correct 9 ms 9448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 2136 KB Output is correct
13 Correct 62 ms 63828 KB Output is correct
14 Correct 245 ms 234680 KB Output is correct
15 Correct 598 ms 514640 KB Output is correct
16 Runtime error 600 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 5 ms 6236 KB Output is correct
4 Correct 9 ms 9448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 2136 KB Output is correct
13 Correct 62 ms 63828 KB Output is correct
14 Correct 245 ms 234680 KB Output is correct
15 Correct 598 ms 514640 KB Output is correct
16 Runtime error 600 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -