Submission #466428

#	Time	Username	Problem	Language	Result	Execution time	Memory
466428		BrainForces	Klasika (COCI20_klasika)	C++14	0 / 110	85 ms	24084 KiB

klasika

#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;
    }

    return ans;
}

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

    rof0(i,(int)s.size()-1) {
        ans += (s[i] == '0') * 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(0, MP(id, 0)));
        } else
            query.pb(MP(1, 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 (stderr)

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:147:5: note: in expansion of macro 'rof0'
  147 |     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:158:5: note: in expansion of macro 'for0'
  158 |     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:202:5: note: in expansion of macro 'for0'
  202 |     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:219:5: note: in expansion of macro 'for0'
  219 |     for0(q, n) {
      |     ^~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44