oj.uz

Submission #475448

# Submission time Handle Problem Language Result Execution time Memory
475448 2021-09-22T13:58:32 Z NSG Klasika (COCI20_klasika) C++14
110 / 110
 2556 ms 434840 KB 
///giangcbg - TST 2022.
#include <bits/stdc++.h>
#define reset(x, val) memset((x), (val), sizeof (x))
#define bit(X, i) (((X) >> (i)) & 1)
#define all(X) (X).begin(), (X).end()
#define on(X,i) (X|(1<<i))
#define off(X,i) (X^(1<<i))
#define cntbit(X) __builtin_popcountll(X)
#define pb push_back
#define ep emplace_back
#define fi first
#define se second
using namespace std;

const char ginp[]="KLASIKA.INP";
const char gout[]="KLASIKA.OUT";

void debug_out() { cerr << '\n'; }
template <typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T)
{
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void read() {}
template <typename Head, typename ...Tail>
void read(Head &H, Tail &...T)
{
    register char c;
    bool sign = 0;
    for (c = getchar(); !isdigit(c); c = getchar())
        if (c == '-') sign = !sign;
    H = c - '0';
    for (c = getchar();  isdigit(c); c = getchar())
        H = H * 10 + c - '0';
    if (sign) H = -H;
    read(T...);
}

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <int, ii> iii;
typedef vector <int> vi;
typedef vector <ii> vii;

mt19937 rd(chrono :: steady_clock :: now().time_since_epoch().count());
#define rand rd
ll Rand(ll l, ll h) { return l + rand() % (h - l + 1); }

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

const int N = 2e5 + 5;
const int oo = 1e9 + 7;

struct query
{
    string s;
    int a,b;
};

struct Trie
{
    Trie *c[2];
    set <int> s;
    Trie()
    {
        c[0] = c[1] = nullptr;
        s.clear();
    }
};

Trie *root;

int m,n;
query q[N];
vi g[N];
int in[N], out[N], f[N];

void enter()
{
    cin >> m;
    n = 1;
    f[1] = 0; ///sumXor
    for (int i = 1; i <= m; i++) 
    {
        cin >> q[i].s >> q[i].a >> q[i].b;
        //debug(q[i].s, q[i].a, q[i].b);
        if (q[i].s == "Add") 
        {
            ++n;
            g[q[i].a].pb(n);
            f[n] = f[q[i].a] ^ q[i].b; 
            q[i].a = n; q[i].b = f[n];
        }
    }
}

void dfs(int u)
{
    in[u] = ++in[0];
    for (int v : g[u]) dfs(v);
    out[u] = ++in[0];
}

void Add(int x, int time)
{
    Trie *p = root;
    for (int i = 30; i >= 0; i--)
    {
        int id = bit(x,i);
        if (p -> c[id] == nullptr) p -> c[id] = new Trie();
        p = p -> c[id];
        p -> s.insert(time);
    }
}

bool check(Trie *p, int b)
{
    auto it = p->s.lower_bound(in[b]);
    if (it == p->s.end() || *it > out[b]) return 0;
    return 1;
}

int Find(int a, int b)
{
    Trie *p = root;
    int x = f[a], res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int id = bit(x,i);
        if (p -> c[!id] != nullptr && check(p -> c[!id], b))
        {
            res |= (1<<i);
            p = p -> c[!id];
        }
        else p = p -> c[id];
    }
    return res;
}

void solve()
{
    dfs(1);
    root = new Trie();
    Add(f[1], in[1]);
    for (int i = 1; i <= m; i++) 
    {
        if (q[i].s == "Query") cout << Find(q[i].a, q[i].b) << '\n';
        else Add(q[i].b, in[q[i].a]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

    #ifndef ONLINE_JUDGE
    
    //freopen(ginp, "r", stdin);
    //freopen(gout, "w", stdout);

    #endif // ONLINE_JUDGE

    enter();
    solve();

    cerr << "\nTime : " << clock() << "ms\n";
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13004 KB Output is correct
2 Correct 9 ms 13104 KB Output is correct
3 Correct 8 ms 13228 KB Output is correct
4 Correct 9 ms 13360 KB Output is correct
5 Correct 9 ms 12896 KB Output is correct
6 Correct 7 ms 13068 KB Output is correct
7 Correct 8 ms 13132 KB Output is correct
8 Correct 8 ms 13388 KB Output is correct
9 Correct 7 ms 13024 KB Output is correct
10 Correct 7 ms 13132 KB Output is correct
11 Correct 8 ms 13260 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13004 KB Output is correct
2 Correct 9 ms 13104 KB Output is correct
3 Correct 8 ms 13228 KB Output is correct
4 Correct 9 ms 13360 KB Output is correct
5 Correct 9 ms 12896 KB Output is correct
6 Correct 7 ms 13068 KB Output is correct
7 Correct 8 ms 13132 KB Output is correct
8 Correct 8 ms 13388 KB Output is correct
9 Correct 7 ms 13024 KB Output is correct
10 Correct 7 ms 13132 KB Output is correct
11 Correct 8 ms 13260 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct
13 Correct 10 ms 14156 KB Output is correct
14 Correct 12 ms 15492 KB Output is correct
15 Correct 14 ms 16716 KB Output is correct
16 Correct 15 ms 17868 KB Output is correct
17 Correct 11 ms 14144 KB Output is correct
18 Correct 12 ms 15420 KB Output is correct
19 Correct 14 ms 16588 KB Output is correct
20 Correct 15 ms 17740 KB Output is correct
21 Correct 11 ms 14156 KB Output is correct
22 Correct 13 ms 15480 KB Output is correct
23 Correct 14 ms 16648 KB Output is correct
24 Correct 15 ms 17740 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 127636 KB Output is correct
2 Correct 1224 ms 232464 KB Output is correct
3 Correct 1724 ms 333100 KB Output is correct
4 Correct 2170 ms 434192 KB Output is correct
5 Correct 753 ms 126196 KB Output is correct
6 Correct 1323 ms 229512 KB Output is correct
7 Correct 1919 ms 328428 KB Output is correct
8 Correct 2396 ms 427480 KB Output is correct
9 Correct 711 ms 125724 KB Output is correct
10 Correct 1307 ms 230204 KB Output is correct
11 Correct 1790 ms 330768 KB Output is correct
12 Correct 2339 ms 429476 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13004 KB Output is correct
2 Correct 9 ms 13104 KB Output is correct
3 Correct 8 ms 13228 KB Output is correct
4 Correct 9 ms 13360 KB Output is correct
5 Correct 9 ms 12896 KB Output is correct
6 Correct 7 ms 13068 KB Output is correct
7 Correct 8 ms 13132 KB Output is correct
8 Correct 8 ms 13388 KB Output is correct
9 Correct 7 ms 13024 KB Output is correct
10 Correct 7 ms 13132 KB Output is correct
11 Correct 8 ms 13260 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct
13 Correct 10 ms 14156 KB Output is correct
14 Correct 12 ms 15492 KB Output is correct
15 Correct 14 ms 16716 KB Output is correct
16 Correct 15 ms 17868 KB Output is correct
17 Correct 11 ms 14144 KB Output is correct
18 Correct 12 ms 15420 KB Output is correct
19 Correct 14 ms 16588 KB Output is correct
20 Correct 15 ms 17740 KB Output is correct
21 Correct 11 ms 14156 KB Output is correct
22 Correct 13 ms 15480 KB Output is correct
23 Correct 14 ms 16648 KB Output is correct
24 Correct 15 ms 17740 KB Output is correct
25 Correct 701 ms 127636 KB Output is correct
26 Correct 1224 ms 232464 KB Output is correct
27 Correct 1724 ms 333100 KB Output is correct
28 Correct 2170 ms 434192 KB Output is correct
29 Correct 753 ms 126196 KB Output is correct
30 Correct 1323 ms 229512 KB Output is correct
31 Correct 1919 ms 328428 KB Output is correct
32 Correct 2396 ms 427480 KB Output is correct
33 Correct 711 ms 125724 KB Output is correct
34 Correct 1307 ms 230204 KB Output is correct
35 Correct 1790 ms 330768 KB Output is correct
36 Correct 2339 ms 429476 KB Output is correct
37 Correct 1282 ms 128752 KB Output is correct
38 Correct 1925 ms 232572 KB Output is correct
39 Correct 2167 ms 335904 KB Output is correct
40 Correct 2524 ms 434840 KB Output is correct
41 Correct 1394 ms 126636 KB Output is correct
42 Correct 1903 ms 229496 KB Output is correct
43 Correct 2227 ms 328684 KB Output is correct
44 Correct 2516 ms 426724 KB Output is correct
45 Correct 1577 ms 125984 KB Output is correct
46 Correct 2015 ms 230224 KB Output is correct
47 Correct 2419 ms 329492 KB Output is correct
48 Correct 2556 ms 429412 KB Output is correct