oj.uz

Submission #466436

# Submission time Handle Problem Language Result Execution time Memory
466436 2021-08-19T09:13:31 Z BrainForces Klasika (COCI20_klasika) C++11
110 / 110
 3081 ms 472576 KB 
#include <bits/stdc++.h>

using namespace std;

// Templates here
template<typename T1, typename T2, typename T3>
class triple {
public:
    T1 first;
    T2 second;
    T3 third;

    triple() {
        first = 0;
        second = 0;
        third = 0;
    }
};

// Typedefs here
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef set<int> si;
typedef set<ll> sl;
typedef set<pii> spii;
typedef set<pll> spll;
typedef map<string, int> mpsi;
typedef map<string, ll> mpsl;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;

// Defines here
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define forla(i, a, b) for(ll (i)=(a);(i)<(b);(i)++)
#define for0(i, b) fora((i),0,(b))
#define forl0(i, b) forla((i),0,(b))
#define rofa(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define rofla(i, a, b) for(ll (i)=(a);(i)>=(b);(i)--)
#define rof0(i, a) rofa((i),(a),0)
#define rofl0(i, a) rofla((i),(a),0)
#define forag(i, a, b, g) for(int (i)=(a);(i)<(b);(i)+=(g))
#define forlag(i, a, b, g) for(ll (i)=(a);(i)<(b);(i)+=(g))
#define for0g(i, b, g) forag((i),0,(b),(g))
#define forl0g(i, b, g) forlag((i),0,(b),(g))
#define rofag(i, a, b, g) for(int (i)=(a);(i)>=(b);(i)-=(g))
#define roflag(i, a, b, g) for(ll (i)=(a);(i)>=(b);(i)-=(g))
#define rof0g(i, a, g) rofag((i),(a),0,(g))
#define rofl0g(i, a, g) roflag((i),(a),0,(g))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define pf push_front
#define MP make_pair
#define F first
#define S second
#define GraphM1(g, n) int (g)[(n)][(n)]
#define GraphM2(g, n) vi (g)[(n)]


// Const variables here
const int maxn = 2e5 + 5;

// Before structs global variables here


// Structs here
struct Node {
    Node *child[2];
    Node *p = nullptr;

    int h, id, cnt;
    si s;

    Node() {
        h = -1;
        id = -1;
        cnt = 0;
        for (auto &i : child)
            i = nullptr;
    }
};

struct Trie {
    Node *root;
    int strType, cnt;

    Trie() {
        strType = '0';
        cnt = 1;

        root = new Node();
        root->h = 0;
        root->id = 1;
    }

    void add(string st, int num) {
        Node *cur = root;
        cur->cnt++;
        cur->s.insert(num);

        for (char c:st) {
            int x = int(c) - strType;

            if (cur->child[x] == nullptr) {
                cur->child[x] = new Node();
                Node *next = cur->child[x];
                
                next->p = cur;
                next->h = cur->h + 1;
                next->id = ++cnt;
            }

            cur = cur->child[x];
            cur->cnt++;
            cur->s.insert(num);
        }
    }
};

// Global variables here
int st[maxn], et[maxn], A[maxn];
vpii g[maxn];
vector<pair<int, pii>> query;
int temp;

// Functions here
string Base2(int x) {
    string ans;

    while (x > 0) {
        ans += to_string(x % 2);
        x /= 2;
    }

    reverse(all(ans));

    while (ans.size() < 31)
        ans = '0' + ans;

    return ans;
}

int Base10(string s) {
    int ans = 0, po = 1;

    rof0(i,(int)s.size()-1) {
        ans += (s[i] == '1') * po;
        po *= 2;
    }

    return ans;
}

void dfs(int x) {
    st[x] = temp++;

    for0(i, (int) g[x].size()) {
        A[g[x][i].F] = (A[x] ^ g[x][i].S);

        dfs(g[x][i].F);
    }

    et[x] = temp++;
}

string find(int x, int y, Node *root) {
    string mab = Base2(A[x]);
    string ans;

    Node *cur = root;

    for (char c:mab) {
        int temp1 = c - '0';
        int temp2 = (temp1 ^ 1);

        if (cur->child[temp2] and !cur->child[temp2]->s.empty()) {
            auto it = cur->child[temp2]->s.lower_bound(st[y]);

            if (it != cur->child[temp2]->s.end() and *it <= et[y]) {
                cur = cur->child[temp2];
                ans += '1';
                continue;
            }
        }

        cur = cur->child[temp1];
        ans += '0';
    }

    return ans;
}

// Main here
int main() {
    IOS

    int n;
    cin >> n;
    int id = 1;

    for0(i, n) {
        string s;
        int a, b;
        cin >> s >> a >> b;
        
        if (s == "Add") {
            g[a].pb(MP(++id, b));
            query.pb(MP(1, MP(id, 0)));
        } else
            query.pb(MP(2, MP(a, b)));

    }

    dfs(1);
    Trie *T = new Trie();
    T->add(Base2(A[1]), st[1]);

    for0(q, n) {
        int qt = query[q].F;

        if (qt == 1) {
            int x = query[q].S.F;
            T->add(Base2(A[x]), st[x]);
        } else {
            int x = query[q].S.F, b = query[q].S.S;
            string ret = find(x, b, T->root);

            cout << Base10(ret) << "\n";
        }
    }

    return 0;
}

Compilation message

klasika.cpp: In function 'int Base10(std::string)':
klasika.cpp:44:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   44 | #define rofa(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
      |                               ^
klasika.cpp:46:20: note: in expansion of macro 'rofa'
   46 | #define rof0(i, a) rofa((i),(a),0)
      |                    ^~~~
klasika.cpp:152:5: note: in expansion of macro 'rof0'
  152 |     rof0(i,(int)s.size()-1) {
      |     ^~~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
      |                               ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
   42 | #define for0(i, b) fora((i),0,(b))
      |                    ^~~~
klasika.cpp:163:5: note: in expansion of macro 'for0'
  163 |     for0(i, (int) g[x].size()) {
      |     ^~~~
klasika.cpp: In function 'int main()':
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
      |                               ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
   42 | #define for0(i, b) fora((i),0,(b))
      |                    ^~~~
klasika.cpp:207:5: note: in expansion of macro 'for0'
  207 |     for0(i, n) {
      |     ^~~~
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'q' [-Wparentheses]
   40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
      |                               ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
   42 | #define for0(i, b) fora((i),0,(b))
      |                    ^~~~
klasika.cpp:224:5: note: in expansion of macro 'for0'
  224 |     for0(q, n) {
      |     ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5540 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 5 ms 5404 KB Output is correct
12 Correct 4 ms 5628 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5540 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 5 ms 5404 KB Output is correct
12 Correct 4 ms 5628 KB Output is correct
13 Correct 9 ms 6568 KB Output is correct
14 Correct 10 ms 7964 KB Output is correct
15 Correct 12 ms 9384 KB Output is correct
16 Correct 13 ms 10700 KB Output is correct
17 Correct 9 ms 6548 KB Output is correct
18 Correct 11 ms 7920 KB Output is correct
19 Correct 14 ms 9248 KB Output is correct
20 Correct 13 ms 10612 KB Output is correct
21 Correct 9 ms 6476 KB Output is correct
22 Correct 11 ms 7884 KB Output is correct
23 Correct 12 ms 9292 KB Output is correct
24 Correct 15 ms 10572 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 131724 KB Output is correct
2 Correct 1543 ms 250092 KB Output is correct
3 Correct 2047 ms 360964 KB Output is correct
4 Correct 2570 ms 472428 KB Output is correct
5 Correct 1087 ms 132428 KB Output is correct
6 Correct 1622 ms 246160 KB Output is correct
7 Correct 2223 ms 354988 KB Output is correct
8 Correct 2870 ms 463652 KB Output is correct
9 Correct 1036 ms 131804 KB Output is correct
10 Correct 1593 ms 247028 KB Output is correct
11 Correct 2231 ms 357680 KB Output is correct
12 Correct 2654 ms 465912 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 4 ms 5540 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 5 ms 5404 KB Output is correct
12 Correct 4 ms 5628 KB Output is correct
13 Correct 9 ms 6568 KB Output is correct
14 Correct 10 ms 7964 KB Output is correct
15 Correct 12 ms 9384 KB Output is correct
16 Correct 13 ms 10700 KB Output is correct
17 Correct 9 ms 6548 KB Output is correct
18 Correct 11 ms 7920 KB Output is correct
19 Correct 14 ms 9248 KB Output is correct
20 Correct 13 ms 10612 KB Output is correct
21 Correct 9 ms 6476 KB Output is correct
22 Correct 11 ms 7884 KB Output is correct
23 Correct 12 ms 9292 KB Output is correct
24 Correct 15 ms 10572 KB Output is correct
25 Correct 971 ms 131724 KB Output is correct
26 Correct 1543 ms 250092 KB Output is correct
27 Correct 2047 ms 360964 KB Output is correct
28 Correct 2570 ms 472428 KB Output is correct
29 Correct 1087 ms 132428 KB Output is correct
30 Correct 1622 ms 246160 KB Output is correct
31 Correct 2223 ms 354988 KB Output is correct
32 Correct 2870 ms 463652 KB Output is correct
33 Correct 1036 ms 131804 KB Output is correct
34 Correct 1593 ms 247028 KB Output is correct
35 Correct 2231 ms 357680 KB Output is correct
36 Correct 2654 ms 465912 KB Output is correct
37 Correct 1465 ms 134936 KB Output is correct
38 Correct 2023 ms 249888 KB Output is correct
39 Correct 2392 ms 363616 KB Output is correct
40 Correct 2688 ms 472576 KB Output is correct
41 Correct 1597 ms 132256 KB Output is correct
42 Correct 2245 ms 245476 KB Output is correct
43 Correct 2804 ms 354832 KB Output is correct
44 Correct 3081 ms 462720 KB Output is correct
45 Correct 1746 ms 131648 KB Output is correct
46 Correct 2307 ms 246664 KB Output is correct
47 Correct 2683 ms 355684 KB Output is correct
48 Correct 2984 ms 465512 KB Output is correct