oj.uz

Submission #708578

# Submission time Handle Problem Language Result Execution time Memory
708578 2023-03-12T03:56:50 Z Quan2003 Klasika (COCI20_klasika) C++17
33 / 110
 5000 ms 80404 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>>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]; 
bool vis[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 if(cur -> c[1]) cur = cur->c[1];
           else break; 
        } 
        else {
            if(cur->c[1]){
                res += (1<<i);
                cur = cur->c[1];
            } 
            else if(cur -> c[0]) cur = cur->c[0];
            else break;
        }
    }
    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); 
     vis[1] = 1;
     for(int i = 0; i < query.size(); i++){
            pii v = query[i].second;
            string s = query[i].first; 
            if(s == "Add"){ 
                  trie[in[v.second] / block].insert(dp[v.second]); 
                  to[in[v.second]] = dp[v.second]; 
                  vis[in[v.second]] = 1;
            }
            else{
                 int start = in[v.second] ;
                 int end = out[v.second];
                 int bkstart = start / block; 
                 int bkend = end / block; 
                 if(start == end){
                      printf("%lld\n",(dp[v.first] xor dp[v.second]));
                      continue; 
                 }
                 if(bkstart == bkend){
                       long long ans = 0; 
                       for(int j = start; j <= end; j++){         
                              if(!vis[j]) continue;
                              ans = max(ans, dp[v.first] xor to[j]);
                 
                       }
                       printf("%lld\n",ans);
                 }
                 else{
                      long long ans = 0; 
                      for(int j = bkstart + 1; j  < bkend; j++){
                             ans = max(ans, trie[j].query(dp[v.first]));
                      }
                      for(int j = start; j / block == bkstart; j++){
                             if(!vis[j]) continue;
                             ans = max(ans, dp[v.first] xor to[j]); 
                      }
                      for(int j = end; j / block == bkend ; j--){
                             if(!vis[j]) 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:65: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]
   65 |       for(int i = 0; i < adj[u].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:73:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   73 |      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:73:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |      scanf("%d",&q);
      |      ~~~~~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 6 ms 6100 KB Output is correct
16 Correct 6 ms 6356 KB Output is correct
17 Correct 4 ms 5332 KB Output is correct
18 Correct 6 ms 5716 KB Output is correct
19 Correct 6 ms 5972 KB Output is correct
20 Correct 6 ms 6228 KB Output is correct
21 Correct 4 ms 5332 KB Output is correct
22 Correct 5 ms 5716 KB Output is correct
23 Correct 5 ms 5972 KB Output is correct
24 Correct 7 ms 6228 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3247 ms 47044 KB Output is correct
2 Execution timed out 5075 ms 80404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 6 ms 6100 KB Output is correct
16 Correct 6 ms 6356 KB Output is correct
17 Correct 4 ms 5332 KB Output is correct
18 Correct 6 ms 5716 KB Output is correct
19 Correct 6 ms 5972 KB Output is correct
20 Correct 6 ms 6228 KB Output is correct
21 Correct 4 ms 5332 KB Output is correct
22 Correct 5 ms 5716 KB Output is correct
23 Correct 5 ms 5972 KB Output is correct
24 Correct 7 ms 6228 KB Output is correct
25 Correct 3247 ms 47044 KB Output is correct
26 Execution timed out 5075 ms 80404 KB Time limit exceeded
27 Halted 0 ms 0 KB -