Submission #930124

#	Time	Username	Problem	Language	Result	Execution time	Memory
930124		duckindog	Klasika (COCI20_klasika)	C++14	33 / 110	1182 ms	524288 KiB

klasika

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
const int N = 3e5 + 10;
int n;
struct Query {
  int a, t;
  Query(int a = 0, int t = 0) : a(a), t(t) {}
};
vector<Query> Q[N];

struct trie {
  int maxBit = 31;
  int it;
  vector<vector<int>> nwt;
  vector<int> t;

  set<int> S;
  map<int, int> tick;
  void add(int val, int time) { 
    S.insert(val);
    if (!tick[val] || tick[val] > time) tick[val] = time;

    int g = 0;
    for (int j = maxBit; j >= 1; --j) { 
      int bit = (val >> j - 1 & 1);

      while (nwt.size() <= g) nwt.push_back(vector<int>(2));

      if (!nwt[g][bit]) nwt[g][bit] = ++it;
      g = nwt[g][bit];

      while (t.size() <= it) t.push_back(N);
      t[g] = min(t[g], time);
    }
  }
  int get(int val, int time) { 
    int g = 0;
    int ret = 0;
    for (int j = maxBit; j >= 1; --j) { 
      int bit = (val >> j - 1 & 1);
      while (nwt.size() <= g) nwt.push_back(vector<int>(2));
      if (nwt[g][!bit] && t[nwt[g][!bit]] <= time) { 
        ret |= (1 << j - 1);
        g = nwt[g][!bit];
      } else g = nwt[g][bit];

    }
    return ret;
  }

  vector<pii> allValues() { 
    vector<pii> ret;
    for (auto &i : S) ret.push_back({i, tick[i]});
    return ret;
  }

  void clear() { 
    nwt.clear();
    t.clear();
    tick.clear();
    S.clear();
  }

} node[N];


vector<pii> ad[N];
int d[N], t[N];
int answer[N];
void dfs(int u, int pre = 0) { 
  int best = 0;
  for (const auto& [v, w] : ad[u]) { 
    if (v == pre) continue;
    dfs(v, u);
    if (!best || node[v].nwt.size() > node[best].nwt.size()) best = v;
  }
  swap(node[u], node[best]);
  for (const auto& [v, w] : ad[u]) { 
    if (v == pre || v == best) continue;
    for (auto &i : node[v].allValues()) node[u].add(i.first, i.second);
    node[v].clear();
  }
  node[u].add(d[u], t[u]);
  for (const auto& [a, time] : Q[u]) answer[time] = node[u].get(d[a], time);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
  
  cin >> n;
  int cnt = 1;
  for (int i = 1; i <= n; ++i) { 
    string ty;
    int x, y; 
    cin >> ty >> x >> y;
    if (ty == "Add") { 
      cnt += 1;
      ad[x].push_back({cnt, y});
      ad[cnt].push_back({x, y});
      d[cnt] = (d[x] ^ y);
      t[cnt] = i;
    } else { 
      Q[y].push_back(Query(x, i));
    }
  }

  memset(answer, -1, sizeof answer);
  dfs(1);
  for (int i = 1; i <= n; ++i) 
    if (answer[i] != -1) cout << answer[i] << "\n";
}

Compilation message (stderr)

klasika.cpp: In member function 'void trie::add(int, int)':
klasika.cpp:30:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   30 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:32:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |       while (nwt.size() <= g) nwt.push_back(vector<int>(2));
      |              ~~~~~~~~~~~^~~~
klasika.cpp:37:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |       while (t.size() <= it) t.push_back(N);
      |              ~~~~~~~~~^~~~~
klasika.cpp: In member function 'int trie::get(int, int)':
klasika.cpp:45:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   45 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:46:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |       while (nwt.size() <= g) nwt.push_back(vector<int>(2));
      |              ~~~~~~~~~~~^~~~
klasika.cpp:48:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |         ret |= (1 << j - 1);
      |                      ~~^~~
klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:77:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |   for (const auto& [v, w] : ad[u]) {
      |                    ^
klasika.cpp:83:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for (const auto& [v, w] : ad[u]) {
      |                    ^
klasika.cpp:89:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (const auto& [a, time] : Q[u]) answer[time] = node[u].get(d[a], time);
      |                    ^

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44