oj.uz

Submission #708559

# Submission time Handle Problem Language Result Execution time Memory
708559 2023-03-12T03:37:03 Z Quan2003 Klasika (COCI20_klasika) C++17
33 / 110
 5000 ms 37948 KB 
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
#define block 472
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>>query; 
int timer = 1;
int in[N + 1],out[N + 1];
long long dp[N + 1]; 
long long blk[N + 1];
long long to[N + 1]; 
template<class T> struct Trie {
    struct Node {
        Node *c[2];
    };
    Node *root = new Node(); 
    void insert(int x){
      Node *cur = root;
      for(int i = 30; i >= 0; i--){
        if(x&(1<<i)){
            if(!cur->c[1])  cur->c[1] = new Node();
            cur = cur->c[1];
        } else {
            if(!cur->c[0])  cur->c[0] = new Node();
            cur = cur->c[0];
           }
       }
   } 
   long long query(int x){
      long long res = 0;
      Node *cur = root;
      for(int i = 30; i >= 0; i--){
         if(x&(1<<i)){
            if(cur->c[0]){
                res += (1<<i);
                cur = cur->c[0];
            } 
           else cur = cur->c[1];
        } else {
            if(cur->c[1]){
                res += (1<<i);
                cur = cur->c[1];
            } 
            else cur = cur->c[0];
        }
    }
    return res;
   }
};

Trie<long long>trie[block + 1];
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 - 1;
}
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; 
              query.push_back({s,{u,node}}); 
          }
          else{
              query.push_back({s,{u,w}}); 
          }
     }
     dfs(1,0); 
     for(int i = 1; i <= n; i++){
           blk[i] = i / block;
     }
     memset(to, -1, sizeof(to)); 
     to[1] = 0; 
     for(int i = 0; i < query.size(); i++){
            pii v = query[i].second;
            string s = query[i].first; 
            if(s == "Add"){ 
                  trie[blk[v.second]].insert(dp[v.second]); 
                  to[in[v.second]] = dp[v.second]; 
            }
            else{
                 int start = in[v.second];
                 int end = out[v.second];
                 if(start == end){
                      printf("%lld\n",(dp[v.first] xor dp[v.second]));
                      continue; 
                 }
                 if(blk[start] == blk[end]){
                       long long ans = 0; 
                       for(int j = start; j <= end; j++){         
                              if(to[j] < 0) continue;
                              ans = max(ans, dp[v.first] xor to[j]);
                 
                       }
                       printf("%lld\n",ans);
                 }
                 else{
                      long long ans = 0; 
                      for(int j = blk[start] + 1; j < blk[end]; j++){
                             ans = max(ans, trie[j].query(dp[v.first]));
                      }
                      for(int j = start; j / block == blk[start]; j++){
                             if(to[j] < 0) continue;
                             ans = max(ans, dp[v.first] xor to[j]); 
                      }
                      for(int j = end; j / block == blk[end]; j--){
                             if(to[j] < 0) continue; 
                             ans = max(ans, dp[v.first] xor to[j]); 
                      }
                      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:89: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]
   89 |      for(int i = 0; i < query.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 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 5 ms 6680 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 5 ms 6744 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 5 ms 6612 KB Output is correct
12 Correct 5 ms 6740 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 5 ms 6680 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 5 ms 6744 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 5 ms 6612 KB Output is correct
12 Correct 5 ms 6740 KB Output is correct
13 Correct 6 ms 7008 KB Output is correct
14 Correct 9 ms 7252 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 10 ms 7800 KB Output is correct
17 Correct 6 ms 6924 KB Output is correct
18 Correct 6 ms 7252 KB Output is correct
19 Correct 6 ms 7452 KB Output is correct
20 Correct 7 ms 7652 KB Output is correct
21 Correct 6 ms 6996 KB Output is correct
22 Correct 7 ms 7252 KB Output is correct
23 Correct 9 ms 7508 KB Output is correct
24 Correct 7 ms 7764 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 37948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 5 ms 6680 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 5 ms 6744 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 5 ms 6612 KB Output is correct
12 Correct 5 ms 6740 KB Output is correct
13 Correct 6 ms 7008 KB Output is correct
14 Correct 9 ms 7252 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 10 ms 7800 KB Output is correct
17 Correct 6 ms 6924 KB Output is correct
18 Correct 6 ms 7252 KB Output is correct
19 Correct 6 ms 7452 KB Output is correct
20 Correct 7 ms 7652 KB Output is correct
21 Correct 6 ms 6996 KB Output is correct
22 Correct 7 ms 7252 KB Output is correct
23 Correct 9 ms 7508 KB Output is correct
24 Correct 7 ms 7764 KB Output is correct
25 Execution timed out 5036 ms 37948 KB Time limit exceeded
26 Halted 0 ms 0 KB -