oj.uz

Submission #589817

# Submission time Handle Problem Language Result Execution time Memory
589817 2022-07-05T10:21:32 Z nguyen31hoang08minh2003 Klasika (COCI20_klasika) C++14
33 / 110
 116 ms 14432 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()
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 BinaryTrie {
private:
    int length, depth;
    vector<array<int, 2> > trie;
public:
    BinaryTrie(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];
            else {
                res |= 1 << i;
                x = trie[x][y];
            }
        }
        return res;
    }
};

int q;

void subtask2() {
    vi h(2);
    vii p(2);
    string t;
    vvii adj(2);
    int x, y, a, b, n = 1, res, g;
    const function<int(int, int)> findDistance = [&](int x, int y) -> int {
        int res = 0;
        for (; h[x] > h[y]; x = p[x].se)
            res ^= p[x].fi;
        for (; h[y] > h[x]; y = p[y].se)
            res ^= p[y].fi;
        while (x != y) {
            res ^= p[x].fi ^ p[y].fi;
            x = p[x].se;
            y = p[y].se;
        }
        return res;
    };
    const function<void(int, int)> dfs = [&res, &adj, &g, &dfs](const int u, const int d) {
        maxi(res, g ^ d);
        for (const auto &[w, v] : adj[u])
            dfs(v, d ^ w);
    };
    fort(_, 1, q) {
        cin >> t;
        if (t == "Add") {
            cin >> x >> y;
            adj.pb(vii());
            adj[x].emplace_back(y, ++n);
            h.pb(h[x] + 1);
            p.emplace_back(y, x);
        } else {
            cin >> a >> b;
            res = g = findDistance(a, b);
            dfs(b, 0);
            cout << res << '\n';
        }
    }
}

void subtask3() {
    vi h(2);
    string t;
    vvii adj(2);
    BinaryTrie trie(30);
    int x, y, a, b, n = 1;
    fort(_, 1, q) {
        cin >> t;
        if (t == "Add") {
            cin >> x >> y;
            adj.pb(vii());
            adj[x].emplace_back(y, ++n);
            h.pb(h[x] ^ y);
            trie.append(h.back());
        } else {
            cin >> a >> b;
            cout << (h[a] ^ trie.query(h[a])) << '\n';
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> q;
    if (q <= 2000)
        subtask2();
    else
        subtask3();
    return 0;
}

Compilation message

klasika.cpp: In constructor 'BinaryTrie::BinaryTrie(int)':
klasika.cpp:47:28: warning: 'BinaryTrie::trie' will be initialized after [-Wreorder]
   47 |     vector<array<int, 2> > trie;
      |                            ^~~~
klasika.cpp:46:9: warning:   'int BinaryTrie::length' [-Wreorder]
   46 |     int length, depth;
      |         ^~~~~~
klasika.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     BinaryTrie(const int depth): trie(1, {-1, -1}), length(0), depth(depth) {};
      |     ^~~~~~~~~~
klasika.cpp: In lambda function:
klasika.cpp:99:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for (const auto &[w, v] : adj[u])
      |                          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 388 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 3 ms 540 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 396 KB Output is correct
20 Correct 1 ms 472 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 2 ms 372 KB Output is correct
23 Correct 2 ms 456 KB Output is correct
24 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 14432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 388 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 3 ms 540 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 396 KB Output is correct
20 Correct 1 ms 472 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 2 ms 372 KB Output is correct
23 Correct 2 ms 456 KB Output is correct
24 Correct 2 ms 492 KB Output is correct
25 Incorrect 116 ms 14432 KB Output isn't correct
26 Halted 0 ms 0 KB -