oj.uz

Submission #1017337

# Submission time Handle Problem Language Result Execution time Memory
1017337 2024-07-09T07:26:57 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 332 ms 73044 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[1];
int path[N], par[M];
vector<int> sub[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")
	{
	  if(q > 2000)
	    cout << Tries[b] -> query(path[a]) << endl;
	  else
	    {
	      int ans = 0;
	      for(int i : sub[b])
		ans = max(ans, path[i] ^ path[a]);
	      cout << ans << endl;
	    }
	}
      else
	{
	  cnt++;
	  path[cnt] = path[a] ^ b;
	  if(q > 2000)
	    Tries[1] -> insert(path[cnt]);
	  else
	    {
	      par[cnt] = a;
	      int cur = cnt;
	      while(cur > 0)
		{
		  sub[cur].push_back(cnt);
		  cur = par[cur];
		}
	    }
	}
    }
  
  return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:41:10: warning: array subscript 1 is above array bounds of 'node* [1]' [-Warray-bounds]
   41 |   Tries[1] = new node();
      |   ~~~~~~~^
klasika.cpp:32:7: note: while referencing 'Tries'
   32 | node *Tries[1];
      |       ^~~~~
klasika.cpp:65:13: warning: array subscript 1 is above array bounds of 'node* [1]' [-Warray-bounds]
   65 |      Tries[1] -> insert(path[cnt]);
      |      ~~~~~~~^
klasika.cpp:32:7: note: while referencing 'Tries'
   32 | node *Tries[1];
      |       ^~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 22100 KB Output is correct
2 Correct 302 ms 41016 KB Output is correct
3 Correct 283 ms 56988 KB Output is correct
4 Correct 245 ms 72492 KB Output is correct
5 Correct 332 ms 23888 KB Output is correct
6 Correct 298 ms 40960 KB Output is correct
7 Correct 290 ms 57172 KB Output is correct
8 Correct 267 ms 72632 KB Output is correct
9 Correct 316 ms 23796 KB Output is correct
10 Correct 320 ms 41072 KB Output is correct
11 Correct 268 ms 57424 KB Output is correct
12 Correct 269 ms 73044 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -