Submission #198342

#	Time	Username	Problem	Language	Result	Execution time	Memory
198342		cjoa	Klasika (COCI20_klasika)	C++11	110 / 110	4500 ms	374116 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];
      set<int> dfs_start_times;
      BinaryTrieNode() {
         child[0] = child[1] = -1;
      }
   };

   vector<BinaryTrieNode> NODES;

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

   int root;
   static const int NUM_BITS = 30;

public:
   BinaryTrie(int N) : root(-1) {
      NODES.reserve(NUM_BITS * N + 1);
   }

   void insert(int x, int t) {
      if (root < 0)
         root = newNode();
      NODES[root].dfs_start_times.insert(t);
      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;
         }
         NODES[nxt].dfs_start_times.insert(t);
         cur = nxt;
      }
   }

   inline bool has_dfs_time(int id, int from_time, int to_time) {
      const set<int>& T = NODES[id].dfs_start_times;
      return T.upper_bound(to_time) != T.lower_bound(from_time);
      /*
      for (int t : T) {
         if (from_time <= t && t <= to_time)
            return true;
      }
      return false;
      */
   }

   int get_max_xor(int x, int from_time, int to_time) {
      if (root < 0 || !has_dfs_time(root, from_time, to_time))
         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 || !has_dfs_time(nxt, from_time, to_time)) {
            nxt = NODES[cur].child[k ^ 1];
         // assert(nxt >= 0);
         }
         else
            res |= 1<<j;
         cur = nxt;
      }
      return res;
   }
};



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;
}


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

   int NN = 1;
   for (Operation op : operations) {
   // fprintf(stderr, "Operation %d\n", op.id);
      if (op.type == 'A') {
         int v = NN++;
         trie.insert( xorsum_to_root[v], dfs_start[v] );
      }
      else {
         int u = op.param1-1, v = op.param2-1;
         int res = trie.get_max_xor( xorsum_to_root[u],
                                     dfs_start[v], dfs_end[v]);
         printf("%d\n", res);
      }
   }
   
// sleep(10);
   
   return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main(int, char**)':
klasika.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Q);
    ~~~~~^~~~~~~~~~
klasika.cpp:140: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: 33 / 33
• Subtask 4: 44 / 44