oj.uz

Submission #589922

# Submission time Handle Problem Language Result Execution time Memory
589922 2022-07-05T11:54:32 Z nguyen31hoang08minh2003 Klasika (COCI20_klasika) C++14
33 / 110
 980 ms 524288 KB 
/*
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|
|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|
|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|
|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|
|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|
|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|
|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|
|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|
|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
*/
#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;
    }
};

class SegmentTree {
private:
    int n;
    vector<Trie> it;

    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].append(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);
    }

    int query(const int ql, const int qr, const int mask, const int i, const int l, const int r) const {
        if (qr < l || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return it[i].query(mask);
        const int m = l + r >> 1;
        return max(query(ql, qr, mask, i << 1, l, m), query(ql, qr, mask, i << 1 | 1, m + 1, r));
    };

public:
    SegmentTree(): n(0) {};
    SegmentTree(const int n): n(n), it(n + 5 << 2, Trie(30)) {};

    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, Trie(30));
    }

    int query(const int ql, const int qr, const int mask) const {
        return query(ql, qr, mask, 1, 1, n);
    }
};

const int maxQ = 200005;

vii adj[maxQ];
SegmentTree it;
int q, n = 1, t;
array<int, maxQ> h, num, d;
vector<tuple<string, int, int> > queries;

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 == "Add") {
            adj[x].emplace_back(y, ++n);
            h[n] = h[x] ^ y;
        }
    }
    it.resize(n);
    dfs(1);
    it.update(num[1], 0);
    t = 1;
    for (const auto &[z, x, y] : queries) {
        if (z == "Add") {
            ++t;
            it.update(num[t], h[t]);
            continue;
        }
        cout << it.query(subtree(y), h[x]) << '\n';
    }
}

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

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:90:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         const int m = l + r >> 1;
      |                       ~~^~~
klasika.cpp: In member function 'int SegmentTree::query(int, int, int, int, int, int) const':
klasika.cpp:100:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         const int m = l + r >> 1;
      |                       ~~^~~
klasika.cpp: In constructor 'SegmentTree::SegmentTree(int)':
klasika.cpp:106:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  106 |     SegmentTree(const int n): n(n), it(n + 5 << 2, Trie(30)) {};
      |                                        ~~^~~
klasika.cpp: In member function 'void SegmentTree::resize(int)':
klasika.cpp:114:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  114 |         newSize = n + 5 << 2;
      |                   ~~^~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:134:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |     for (const auto &[w, v] : adj[u]) {
      |                      ^
klasika.cpp: In function 'void solve()':
klasika.cpp:146:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |     for (auto &[z, x, y] : queries) {
      |                ^
klasika.cpp:157:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |     for (const auto &[z, x, y] : queries) {
      |                      ^

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 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 4 ms 5280 KB Output is correct
12 Correct 3 ms 5460 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 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 4 ms 5280 KB Output is correct
12 Correct 3 ms 5460 KB Output is correct
13 Correct 6 ms 6356 KB Output is correct
14 Correct 9 ms 7764 KB Output is correct
15 Correct 10 ms 9040 KB Output is correct
16 Correct 12 ms 10956 KB Output is correct
17 Correct 6 ms 6356 KB Output is correct
18 Correct 8 ms 7892 KB Output is correct
19 Correct 10 ms 8912 KB Output is correct
20 Correct 13 ms 10700 KB Output is correct
21 Correct 7 ms 6356 KB Output is correct
22 Correct 9 ms 7724 KB Output is correct
23 Correct 10 ms 8904 KB Output is correct
24 Correct 13 ms 10576 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 171924 KB Output is correct
2 Correct 674 ms 342796 KB Output is correct
3 Correct 980 ms 509472 KB Output is correct
4 Runtime error 946 ms 524288 KB Execution killed with signal 9
5 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 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5460 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 4 ms 5280 KB Output is correct
12 Correct 3 ms 5460 KB Output is correct
13 Correct 6 ms 6356 KB Output is correct
14 Correct 9 ms 7764 KB Output is correct
15 Correct 10 ms 9040 KB Output is correct
16 Correct 12 ms 10956 KB Output is correct
17 Correct 6 ms 6356 KB Output is correct
18 Correct 8 ms 7892 KB Output is correct
19 Correct 10 ms 8912 KB Output is correct
20 Correct 13 ms 10700 KB Output is correct
21 Correct 7 ms 6356 KB Output is correct
22 Correct 9 ms 7724 KB Output is correct
23 Correct 10 ms 8904 KB Output is correct
24 Correct 13 ms 10576 KB Output is correct
25 Correct 356 ms 171924 KB Output is correct
26 Correct 674 ms 342796 KB Output is correct
27 Correct 980 ms 509472 KB Output is correct
28 Runtime error 946 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -