Submission #198340

#	Time	Username	Problem	Language	Result	Execution time	Memory
198340		cjoa	Klasika (COCI20_klasika)	C++11	33 / 110	1191 ms	524288 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;

class 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 size;
   int root;
   static const int NUM_BITS = 30;

public:
   BinaryTrie() : size(0) {
      root = newNode();
   }

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

   void insert(int x) {
      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;
      }
      ++size;
   }
   int get_max_xor(int x) {
      if (size == 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;


class SegmentTree {
   int N;
   vector<BinaryTrie> tree;
   void insert(int pos, int x, int id, int L, int R) {
      if (pos < L || pos > R) return;
      tree[id].insert(x);
      if (L == R)
         return;
      int mid = L + (R-L)/2;
      insert(pos, x, id*2, L, mid);
      insert(pos, x, id*2+1, mid+1, R);
   }
   int query(int p, int q, int x, int id, int L, int R) {
      if (q < L || p > R) return 0;
      if (p <= L && R <= q)
         return tree[id].get_max_xor(x);

      const int mid = L + (R-L)/2;
      return max( query(p, q, x, id*2, L, mid),
                  query(p, q, x, id*2+1, mid+1, R) );
   }
public:
   SegmentTree(int _N) : N(_N) {
      tree.resize(4*_N+100);
   }
   void insert(int pos, int x) {
      insert(pos, x, 1, 0, N-1);
   }
   int query(int p, int q, int x) {
      return query(p, q, x, 1, 0, N-1);
   }
};



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


struct Edge {
   int to, weight;
};


#define MAXN 200001
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;
}


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

   vector<Operation> operations;
   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 segm_tree(N);
   segm_tree.insert( dfs_start[0], xorsum_to_root[0] );

   int NN = 1;
   for (Operation op : operations) {
      if (op.type == 'A') {
         int v = NN++;
         segm_tree.insert( dfs_start[v], xorsum_to_root[v] );
      }
      else {
         int u = op.param1-1, v = op.param2-1;
         int res = segm_tree.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:157:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Q);
    ~~~~~^~~~~~~~~~
klasika.cpp:163: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