Submission #591233

#TimeUsernameProblemLanguageResultExecution timeMemory
591233nguyen31hoang08minh2003Klasika (COCI20_klasika)C++14
110 / 110
1026 ms135696 KiB
/* +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-| |\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/| |/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/| |/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\| |-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-| |\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/| |/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/| |/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\| |-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ */ #include <bits/stdc++.h> #define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i) #define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i) #define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i) #define fi first #define se second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define subtree(x) num[x], num[x] + d[x] - 1 using namespace std; using ll = long long; using ld = long double; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef unsigned long long ull; typedef pair<int, int> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; class Trie { private: int length, depth; vector<array<int, 2> > trie; public: Trie(const int depth): trie(1, {-1, -1}), length(0), depth(depth) {}; void append(const int mask) { int x = 0, y; ford(i, depth, 0) { y = ((mask >> i) & 1); if (trie[x][y] < 0) { trie[x][y] = ++length; trie.push_back({-1, -1}); } x = trie[x][y]; } } int query(const int mask) const { int res = 0, x = 0, y; ford(i, depth, 0) { y = ((mask >> i) & 1) ^ 1; if (trie[x][y] < 0) { x = trie[x][y ^ 1]; if (x < 0) return 0; } else { res |= 1 << i; x = trie[x][y]; } } return res; } }; const int maxQ = 200005; vii adj[maxQ]; int q, n = 1, t; array<int, maxQ> h, num, d, ans; vector<tuple<string, int, int> > queries; class SegmentTree { private: int n; vector<vector<pair<bool, int> > > it; // first -> false : update // first -> true : query void update(const int q, const int mask, const int i, const int l, const int r) { if (q < l || r < q) return; it[i].emplace_back(false, mask); if (l == r) return; const int m = l + r >> 1; update(q, mask, i << 1, l, m); update(q, mask, i << 1 | 1, m + 1, r); } void query(const int ql, const int qr, const int value, const int i, const int l, const int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { it[i].emplace_back(true, value); return; } const int m = l + r >> 1; query(ql, qr, value, i << 1, l, m); query(ql, qr, value, i << 1 | 1, m + 1, r); }; void run(const int i, const int l, const int r) { if (l < r) { const int m = l + r >> 1; run(i << 1, l, m); run(i << 1 | 1, m + 1, r); } Trie trie(30); for (const auto &[flag, value] : it[i]) if (flag) maxi(ans[value], trie.query(h[get<1>(queries[value])])); else trie.append(value); } public: SegmentTree(): n(0) {}; SegmentTree(const int n): n(n), it(n + 5 << 2) {}; void update(const int q, const int mask) { update(q, mask, 1, 1, n); } void resize(int newSize) { n = newSize; newSize = n + 5 << 2; it.resize(newSize); } void query(const int ql, const int qr, const int value) { return query(ql, qr, value, 1, 1, n); } void run() { run(1, 1, n); } } it; void dfs(const int u) { num[u] = ++t; ++d[u]; for (const auto &[w, v] : adj[u]) { dfs(v); d[u] += d[v]; } }; void input() { cin >> q; queries.resize(q); } void solve() { for (auto &[z, x, y] : queries) { cin >> z >> x >> y; if (z[0] == 'A') { adj[x].emplace_back(y, ++n); h[n] = h[x] ^ y; } } it.resize(n); dfs(1); t = 1; it.update(num[t], h[t]); fore(i, 0, q) { const auto &[z, x, y] = queries[i]; if (z[0] == 'A') { ++t; it.update(num[t], h[t]); } else it.query(subtree(y), i); } it.run(); fore(i, 0, q) { const auto &[z, x, y] = queries[i]; if (z[0] == 'A') continue; cout << ans[i] << '\n'; } } void createInput() { int q = 200000, n = 1; srand(time(NULL)); ofstream input("input.INP"); input << q << '\n'; fore(i, 1, q) { input << "Add " << rand() % n + 1 << ' ' << rand() << '\n'; ++n; } input << "Query " << rand() % n + 1 << ' ' << 1 << '\n'; input.close(); } int main() { #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); input(); solve(); return 0; }

Compilation message (stderr)

klasika.cpp: In constructor 'Trie::Trie(int)':
klasika.cpp:48:28: warning: 'Trie::trie' will be initialized after [-Wreorder]
   48 |     vector<array<int, 2> > trie;
      |                            ^~~~
klasika.cpp:47:9: warning:   'int Trie::length' [-Wreorder]
   47 |     int length, depth;
      |         ^~~~~~
klasika.cpp:50:5: warning:   when initialized here [-Wreorder]
   50 |     Trie(const int depth): trie(1, {-1, -1}), length(0), depth(depth) {};
      |     ^~~~
klasika.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
klasika.cpp:99:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         const int m = l + r >> 1;
      |                       ~~^~~
klasika.cpp: In member function 'void SegmentTree::query(int, int, int, int, int, int)':
klasika.cpp:111:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         const int m = l + r >> 1;
      |                       ~~^~~
klasika.cpp: In member function 'void SegmentTree::run(int, int, int)':
klasika.cpp:118:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |             const int m = l + r >> 1;
      |                           ~~^~~
klasika.cpp:123:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |         for (const auto &[flag, value] : it[i])
      |                          ^
klasika.cpp: In constructor 'SegmentTree::SegmentTree(int)':
klasika.cpp:132:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  132 |     SegmentTree(const int n): n(n), it(n + 5 << 2) {};
      |                                        ~~^~~
klasika.cpp: In member function 'void SegmentTree::resize(int)':
klasika.cpp:140:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  140 |         newSize = n + 5 << 2;
      |                   ~~^~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |     for (const auto &[w, v] : adj[u]) {
      |                      ^
klasika.cpp: In function 'void solve()':
klasika.cpp:168:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |     for (auto &[z, x, y] : queries) {
      |                ^
klasika.cpp:180:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  180 |         const auto &[z, x, y] = queries[i];
      |                     ^
klasika.cpp:189:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  189 |         const auto &[z, x, y] = queries[i];
      |                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...