답안 #1017231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017231	2024-07-09T06:50:26 Z	vjudge1	Klasika (COCI20_klasika)	C++17	44 / 110	583 ms	524288 KB

klasika

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-