Submission #708616

#	Time	Username	Problem	Language	Result	Execution time	Memory
708616		Quan2003	Klasika (COCI20_klasika)	C++17	110 / 110	2551 ms	448056 KiB

klasika

#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
#define block 467
typedef pair<int,int> pii;
const int sz = 4e5 + 1;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = (1 << 32);
long long n,m,k,q,x;
vector<pii>adj[N + 1];
vector<pair<string,pii>>queries; 
int timer = 0;
int in[N + 1],out[N + 1];
long long dp[N + 1]; 
long long blk[N + 1];
long long to[N + 1]; 
bool vis[N + 1];
struct Node {
        set<int>s;
        Node *c[2];
};
Node *root = new Node(); 
void insert(Node *node,int x,int bit,int id){
      node -> s.insert(id); 
      if(bit < 0) return;
      if(x & (1 << bit)){
           if(!node -> c[1]) node -> c[1] = new Node();
           insert(node -> c[1],x,bit - 1,id); 
      }
      else{
           if(!node -> c[0]) node -> c[0] = new Node();
           insert(node -> c[0],x,bit - 1,id); 
      }
} 
long long query(Node *node, int x,int bit, int from, int to){
       if(bit < 0) return 0;
       if(x & (1 << bit)){
            if(!node -> c[0]){
                 return query(node -> c[1],x,bit - 1,from,to); 
            }
            if(node -> c[0] -> s.lower_bound(from) == node -> c[0] -> s.upper_bound(to)){
                 return query(node -> c[1],x,bit - 1,from,to); 
            }
            return (1 << bit) + query(node -> c[0], x, bit - 1, from, to); 
       }
       else{
            if(!node -> c[1]){
                 return query(node -> c[0],x,bit - 1,from,to); 
            }
            if(node -> c[1] -> s.lower_bound(from) == node -> c[1] -> s.upper_bound(to)){
                 return query(node -> c[0],x,bit - 1,from,to); 
            }
            return (1 << bit) + query(node -> c[1], x, bit - 1, from, to); 
       }
     
}
void dfs(int u,int p){
      in[u] = ++timer; 
      for(int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].first;
            if(v == p) continue;   
            dfs(v,u); 
      } 
      out[u] = timer;
}
int main(){
     scanf("%d",&q);
     int node = 1;
     for(int i = 1; i <= q; i++){
          string s; int u,w; 
          cin >> s >> u >> w;
          if(s == "Add"){
              adj[u].push_back({++node,w}); 
              dp[node] = dp[u] xor w; 
              queries.push_back({s,{u,node}}); 
          }
          else{
              queries.push_back({s,{u,w}}); 
          }
     }
     dfs(1,0); 
     insert(root,0,30,in[1]);
     for(int i = 0; i < queries.size(); i++){
            pii v = queries[i].second;
            string s = queries[i].first;
            if(s == "Add"){
                insert(root,dp[v.second],30,in[v.second]);     
            }
            else{
                long long ans = query(root,dp[v.first],30,in[v.second],out[v.second]);
                printf("%lld\n",ans); 
            }
     }
     return 0; 
}

Compilation message (stderr)

klasika.cpp:10:20: warning: left shift count >= width of type [-Wshift-count-overflow]
   10 | const int mod = (1 << 32);
      |                  ~~^~~~~
klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |       for(int i = 0; i < adj[u].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:69:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   69 |      scanf("%d",&q);
      |             ~^  ~~
      |              |  |
      |              |  long long int*
      |              int*
      |             %lld
klasika.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |      for(int i = 0; i < queries.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~
klasika.cpp:69:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |      scanf("%d",&q);
      |      ~~~~~^~~~~~~~~

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