Submission #708572

#TimeUsernameProblemLanguageResultExecution timeMemory
708572Quan2003Klasika (COCI20_klasika)C++17
0 / 110
5009 ms37616 KiB
#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 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); 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[blk[v.second]].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 (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:62: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]
   62 |       for(int i = 0; i < adj[u].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:70:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   70 |      scanf("%d",&q);
      |             ~^  ~~
      |              |  |
      |              |  long long int*
      |              int*
      |             %lld
klasika.cpp:86: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]
   86 |      for(int i = 0; i < query.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
klasika.cpp:103:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  103 |                  if(bkstart = bkend){
      |                     ~~~~~~~~^~~~~~~
klasika.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |      scanf("%d",&q);
      |      ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...