oj.uz

Submission #708544

# Submission time Handle Problem Language Result Execution time Memory
708544 2023-03-12T03:20:31 Z Quan2003 Klasika (COCI20_klasika) C++17
33 / 110
 5000 ms 44924 KB 
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
#define block 448
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 { 
        int cntl=0;
        int cntr=0;
		int l = -1, r = -1; 
	};
	int B;
    int t;
	vector<Node> nodes;
	int newNode() { 
		nodes.emplace_back();
		return nodes.size() - 1;
	}

	void init(int _B) {
		B = _B;
		nodes.clear();
		newNode();
	}

	void insert(int n) {
		int u = 0;
		for (int i = B; i >= 0; i--) {
			if ((n >> i) & 1) {
				if (nodes[u].r == -1) {
					 nodes[u].r = newNode(); 
				}
           nodes[u].cntr++;
				   u = nodes[u].r;
			} 
      else {
				if (nodes[u].l == -1) {
					 nodes[u].l = newNode();
        }
           nodes[u].cntl++;
				   u = nodes[u].l;
			}
		} 
	}
	ll query(int n) {
		int u = 0; 
        ll ans = 0;
		for (int i = B; i >= 0; i--) {
			if ((n >> i) & 1) {
				if (nodes[u].l != -1) {
					u = nodes[u].l;
                    ans += (1ll << i);
				} else {
					u = nodes[u].r;
				}
			} else {
				if (nodes[u].r != -1 ) {
					u = nodes[u].r;
                    ans+=(1ll << i);
				} else {
					u = nodes[u].l;
				}
			}
		}
		return ans;
	}
};
Trie<int>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 = 0; i <= block; i++) trie[i].init(30);
     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:84: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]
   84 |       for(int i = 0; i < adj[u].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:92:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   92 |      scanf("%d",&q);
      |             ~^  ~~
      |              |  |
      |              |  long long int*
      |              int*
      |             %lld
klasika.cpp:113: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]
  113 |      for(int i = 0; i < query.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
klasika.cpp:92:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |      scanf("%d",&q);
      |      ~~~~~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6660 KB Output is correct
5 Correct 4 ms 6640 KB Output is correct
6 Correct 4 ms 6596 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 5 ms 6740 KB Output is correct
12 Correct 4 ms 6740 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6660 KB Output is correct
5 Correct 4 ms 6640 KB Output is correct
6 Correct 4 ms 6596 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 5 ms 6740 KB Output is correct
12 Correct 4 ms 6740 KB Output is correct
13 Correct 6 ms 7152 KB Output is correct
14 Correct 9 ms 7412 KB Output is correct
15 Correct 7 ms 7524 KB Output is correct
16 Correct 7 ms 8012 KB Output is correct
17 Correct 5 ms 7124 KB Output is correct
18 Correct 6 ms 7412 KB Output is correct
19 Correct 6 ms 7368 KB Output is correct
20 Correct 8 ms 7412 KB Output is correct
21 Correct 5 ms 7124 KB Output is correct
22 Correct 5 ms 7412 KB Output is correct
23 Correct 6 ms 7420 KB Output is correct
24 Correct 6 ms 7396 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6660 KB Output is correct
5 Correct 4 ms 6640 KB Output is correct
6 Correct 4 ms 6596 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 5 ms 6740 KB Output is correct
12 Correct 4 ms 6740 KB Output is correct
13 Correct 6 ms 7152 KB Output is correct
14 Correct 9 ms 7412 KB Output is correct
15 Correct 7 ms 7524 KB Output is correct
16 Correct 7 ms 8012 KB Output is correct
17 Correct 5 ms 7124 KB Output is correct
18 Correct 6 ms 7412 KB Output is correct
19 Correct 6 ms 7368 KB Output is correct
20 Correct 8 ms 7412 KB Output is correct
21 Correct 5 ms 7124 KB Output is correct
22 Correct 5 ms 7412 KB Output is correct
23 Correct 6 ms 7420 KB Output is correct
24 Correct 6 ms 7396 KB Output is correct
25 Execution timed out 5044 ms 44924 KB Time limit exceeded
26 Halted 0 ms 0 KB -