oj.uz

Submission #1017231

# Submission time Handle Problem Language Result Execution time Memory
1017231 2024-07-09T06:50:26 Z vjudge1 Klasika (COCI20_klasika) C++17
44 / 110
 583 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 = 2e5+5, M = 2000 + 10;
node *Tries[M];
int path[N], par[M];

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 5980 KB Output is correct
4 Correct 8 ms 9564 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 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 1452 KB Output is correct
12 Correct 2 ms 2140 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 5980 KB Output is correct
4 Correct 8 ms 9564 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 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 1452 KB Output is correct
12 Correct 2 ms 2140 KB Output is correct
13 Correct 69 ms 63828 KB Output is correct
14 Correct 238 ms 234836 KB Output is correct
15 Correct 568 ms 514644 KB Output is correct
16 Runtime error 583 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 24404 KB Output is correct
2 Correct 305 ms 42324 KB Output is correct
3 Correct 387 ms 58412 KB Output is correct
4 Correct 247 ms 74576 KB Output is correct
5 Correct 326 ms 24912 KB Output is correct
6 Correct 276 ms 42324 KB Output is correct
7 Correct 289 ms 58484 KB Output is correct
8 Correct 256 ms 74392 KB Output is correct
9 Correct 308 ms 24664 KB Output is correct
10 Correct 311 ms 42264 KB Output is correct
11 Correct 278 ms 58672 KB Output is correct
12 Correct 272 ms 74324 KB Output is correct

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 5980 KB Output is correct
4 Correct 8 ms 9564 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 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 1452 KB Output is correct
12 Correct 2 ms 2140 KB Output is correct
13 Correct 69 ms 63828 KB Output is correct
14 Correct 238 ms 234836 KB Output is correct
15 Correct 568 ms 514644 KB Output is correct
16 Runtime error 583 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -