Submission #198341

#	Time	Username	Problem	Language	Result	Execution time	Memory
198341		cjoa	Klasika (COCI20_klasika)	C++11	33 / 110	1728 ms	524292 KiB

klasika

#include <cstdio>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cassert>

#include <unistd.h>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

#define DEBUG(x) cerr << #x << ": " << x << endl
#define HIGHESTSETBIT(mask) ( sizeof(int)*8-1-__builtin_clz((mask)) )

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

struct BinaryTrie {
   struct BinaryTrieNode {
      int child[2];
      BinaryTrieNode() {
         child[0] = child[1] = -1;
      }
   };

   static vector<BinaryTrieNode> NODES;

   static int newNode() {
      NODES.push_back( BinaryTrieNode() );
      return int(NODES.size()) - 1;
   }

   int root;
   static const int NUM_BITS = 30;

public:
   BinaryTrie() : root(-1) {
   }

   static void reserve(int N) {
      NODES.reserve(NUM_BITS * N + 1);
   }

   void insert(int x) {
      if (root < 0)
         root = newNode();
      int cur = root;
      for (int j = NUM_BITS-1; j >= 0; --j) {
         int k = (x >> j) & 1;
         int nxt = NODES[cur].child[k];
         if (nxt < 0) {
            nxt = newNode();
            NODES[cur].child[k] = nxt;
         }
         cur = nxt;
      }
   }
   int get_max_xor(int x) {
      if (root < 0)
         return 0;
      int res = 0;
      int cur = root;
      for (int j = NUM_BITS-1; j >= 0; --j) {
         int k = ((x >> j) & 1) ^ 1;  // bit to try
         int nxt = NODES[cur].child[k];
         if (nxt < 0) {
            nxt = NODES[cur].child[k ^ 1];
         // assert(nxt >= 0);
         }
         else
            res |= 1<<j;
         cur = nxt;
      }
      return res;
   }
};

vector<BinaryTrie::BinaryTrieNode> BinaryTrie::NODES;


struct Operation {
   char type;
   int param1, param2;
};

struct Edge {
   int to, weight;
};

#define MAXN 200000
int N;
vector< vector<Edge> > adj;

int xorsum_to_root[MAXN];
int dfs_start[MAXN], dfs_end[MAXN];
int dfs_time;
void dfs1(int u, int x = 0) {
   xorsum_to_root[u] = x;
   dfs_start[u] = ++dfs_time;
   for (Edge e : adj[u])
      dfs1(e.to, x ^ e.weight);
   dfs_end[u] = dfs_time;
}


namespace SegmentTree {

BinaryTrie T[MAXN*2];

int next_power2(int N) {
   int res = 1;
   while (res < N)
      res *= 2;
   return res;
}

void insert(int p, int x) {
   int i = p + N;
   T[i].insert(x);
   for (i /= 2; i > 0; i /= 2) {
      T[i].insert(x);
   }
}

int query(int L, int R, int x) { 
   int resL = 0, resR = 0;
   for (int l = L + N, r = R + N; l <= r; l /= 2, r /= 2) {
      if ((l % 2) == 1) resL = max(resL, T[l++].get_max_xor(x));
      if ((r % 2) == 0) resR = max(T[r--].get_max_xor(x), resR);
   }
   return max(resL, resR);
}


}


int main(int argc, char* argv[]) {
   int Q;
   scanf("%d", &Q);

   vector<Operation> operations;
   operations.reserve(Q);
   REP(q, Q) {
      char oper[6];
      int param1, param2;
      scanf("%s %d %d", oper, &param1, &param2);
      operations.push_back({*oper, param1, param2});
   }

   adj.push_back( vector<Edge>() );
   for (Operation op : operations) {
      if (op.type == 'A') {
         int p = op.param1-1;
         int w = op.param2;
         int v = adj.size();
         adj.push_back( vector<Edge>() );
         adj[p].push_back({v, w});
      }
   }
   
   N = adj.size();
   
   dfs_time = -1;
   dfs1(0);

   adj.clear();

   BinaryTrie::reserve(N);

   SegmentTree::insert( dfs_start[0], xorsum_to_root[0] );

   int NN = 1;
   for (Operation op : operations) {
      if (op.type == 'A') {
         int v = NN++;
         SegmentTree::insert( dfs_start[v], xorsum_to_root[v] );
      }
      else {
         int u = op.param1-1, v = op.param2-1;
         int res = SegmentTree::query( dfs_start[v], dfs_end[v],
                                       xorsum_to_root[u] );
         printf("%d\n", res);
      }
   }

// fprintf(stderr, "nodes = %d\n", SZ(BinaryTrie::NODES));

// sleep(10);

   return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main(int, char**)':
klasika.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Q);
    ~~~~~^~~~~~~~~~
klasika.cpp:158:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%s %d %d", oper, &param1, &param2);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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