oj.uz

Submission #198342

# Submission time Handle Problem Language Result Execution time Memory
198342 2020-01-25T16:29:10 Z cjoa Klasika (COCI20_klasika) C++11
110 / 110
 4500 ms 374116 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 0 ms 632 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 760 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 0 ms 632 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 6 ms 1528 KB Output is correct
14 Correct 8 ms 2552 KB Output is correct
15 Correct 11 ms 3704 KB Output is correct
16 Correct 12 ms 4640 KB Output is correct
17 Correct 7 ms 1528 KB Output is correct
18 Correct 10 ms 2552 KB Output is correct
19 Correct 12 ms 3576 KB Output is correct
20 Correct 13 ms 4560 KB Output is correct
21 Correct 7 ms 1400 KB Output is correct
22 Correct 9 ms 2552 KB Output is correct
23 Correct 11 ms 3548 KB Output is correct
24 Correct 13 ms 4472 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 100380 KB Output is correct
2 Correct 1939 ms 192264 KB Output is correct
3 Correct 2577 ms 280780 KB Output is correct
4 Correct 3175 ms 373772 KB Output is correct
5 Correct 1179 ms 101464 KB Output is correct
6 Correct 2001 ms 192144 KB Output is correct
7 Correct 2877 ms 279192 KB Output is correct
8 Correct 3661 ms 366832 KB Output is correct
9 Correct 1103 ms 101192 KB Output is correct
10 Correct 1888 ms 192788 KB Output is correct
11 Correct 2623 ms 281280 KB Output is correct
12 Correct 3377 ms 368524 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 0 ms 632 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 6 ms 1528 KB Output is correct
14 Correct 8 ms 2552 KB Output is correct
15 Correct 11 ms 3704 KB Output is correct
16 Correct 12 ms 4640 KB Output is correct
17 Correct 7 ms 1528 KB Output is correct
18 Correct 10 ms 2552 KB Output is correct
19 Correct 12 ms 3576 KB Output is correct
20 Correct 13 ms 4560 KB Output is correct
21 Correct 7 ms 1400 KB Output is correct
22 Correct 9 ms 2552 KB Output is correct
23 Correct 11 ms 3548 KB Output is correct
24 Correct 13 ms 4472 KB Output is correct
25 Correct 1211 ms 100380 KB Output is correct
26 Correct 1939 ms 192264 KB Output is correct
27 Correct 2577 ms 280780 KB Output is correct
28 Correct 3175 ms 373772 KB Output is correct
29 Correct 1179 ms 101464 KB Output is correct
30 Correct 2001 ms 192144 KB Output is correct
31 Correct 2877 ms 279192 KB Output is correct
32 Correct 3661 ms 366832 KB Output is correct
33 Correct 1103 ms 101192 KB Output is correct
34 Correct 1888 ms 192788 KB Output is correct
35 Correct 2623 ms 281280 KB Output is correct
36 Correct 3377 ms 368524 KB Output is correct
37 Correct 2343 ms 104164 KB Output is correct
38 Correct 3061 ms 195520 KB Output is correct
39 Correct 3501 ms 286596 KB Output is correct
40 Correct 3762 ms 374116 KB Output is correct
41 Correct 2410 ms 101944 KB Output is correct
42 Correct 3181 ms 192068 KB Output is correct
43 Correct 3780 ms 279384 KB Output is correct
44 Correct 4500 ms 366052 KB Output is correct
45 Correct 2576 ms 101488 KB Output is correct
46 Correct 3335 ms 192732 KB Output is correct
47 Correct 3883 ms 280224 KB Output is correct
48 Correct 4297 ms 368452 KB Output is correct