oj.uz

Submission #708616

# Submission time Handle Problem Language Result Execution time Memory
708616 2023-03-12T04:43:15 Z Quan2003 Klasika (COCI20_klasika) C++17
110 / 110
 2551 ms 448056 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5268 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5268 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 8 ms 7764 KB Output is correct
15 Correct 10 ms 9112 KB Output is correct
16 Correct 11 ms 10196 KB Output is correct
17 Correct 7 ms 6356 KB Output is correct
18 Correct 12 ms 7636 KB Output is correct
19 Correct 12 ms 8976 KB Output is correct
20 Correct 13 ms 10068 KB Output is correct
21 Correct 8 ms 6356 KB Output is correct
22 Correct 9 ms 7636 KB Output is correct
23 Correct 10 ms 8916 KB Output is correct
24 Correct 13 ms 10068 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 128584 KB Output is correct
2 Correct 1401 ms 237400 KB Output is correct
3 Correct 1801 ms 343012 KB Output is correct
4 Correct 2257 ms 447464 KB Output is correct
5 Correct 887 ms 128328 KB Output is correct
6 Correct 1351 ms 233812 KB Output is correct
7 Correct 1837 ms 334976 KB Output is correct
8 Correct 2304 ms 436236 KB Output is correct
9 Correct 877 ms 127924 KB Output is correct
10 Correct 1349 ms 234992 KB Output is correct
11 Correct 1801 ms 337728 KB Output is correct
12 Correct 2195 ms 438856 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5268 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 8 ms 7764 KB Output is correct
15 Correct 10 ms 9112 KB Output is correct
16 Correct 11 ms 10196 KB Output is correct
17 Correct 7 ms 6356 KB Output is correct
18 Correct 12 ms 7636 KB Output is correct
19 Correct 12 ms 8976 KB Output is correct
20 Correct 13 ms 10068 KB Output is correct
21 Correct 8 ms 6356 KB Output is correct
22 Correct 9 ms 7636 KB Output is correct
23 Correct 10 ms 8916 KB Output is correct
24 Correct 13 ms 10068 KB Output is correct
25 Correct 1014 ms 128584 KB Output is correct
26 Correct 1401 ms 237400 KB Output is correct
27 Correct 1801 ms 343012 KB Output is correct
28 Correct 2257 ms 447464 KB Output is correct
29 Correct 887 ms 128328 KB Output is correct
30 Correct 1351 ms 233812 KB Output is correct
31 Correct 1837 ms 334976 KB Output is correct
32 Correct 2304 ms 436236 KB Output is correct
33 Correct 877 ms 127924 KB Output is correct
34 Correct 1349 ms 234992 KB Output is correct
35 Correct 1801 ms 337728 KB Output is correct
36 Correct 2195 ms 438856 KB Output is correct
37 Correct 1497 ms 132068 KB Output is correct
38 Correct 1874 ms 239060 KB Output is correct
39 Correct 2204 ms 345672 KB Output is correct
40 Correct 2356 ms 448056 KB Output is correct
41 Correct 1510 ms 128568 KB Output is correct
42 Correct 2043 ms 233648 KB Output is correct
43 Correct 2338 ms 335304 KB Output is correct
44 Correct 2540 ms 435544 KB Output is correct
45 Correct 1648 ms 128348 KB Output is correct
46 Correct 2072 ms 234944 KB Output is correct
47 Correct 2336 ms 336344 KB Output is correct
48 Correct 2551 ms 438712 KB Output is correct