Submission #1087724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087724		shidou26	Klasika (COCI20_klasika)	C++14	110 / 110	1822 ms	446108 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define all(v) v.begin(), v.end()
#define int long long

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef tuple<string, int, int> query;

const int N = 2e5 + 3;
const int LIM = 2;

struct node {
    set<int> jikan;
    node* children[LIM];
};

int q, n = 1;
int child[N];
query queries[N];
vector<ii> adj[N];

int timer = 0;
int h[N], d[N], tin[N], tout[N];
node *root = new node();

void prepare() {

}

void input() {
    cin >> q;

    for(int i = 1; i <= q; i++) {
        string s; int a, b; cin >> s >> a >> b;
        queries[i] = query(s, a, b);
        if(s[0] == 'A') {
            adj[a].push_back(ii(++n, b));
            child[i] = n;
        }
    }
}

void dfs(int u) {
    tin[u] = ++timer;
    for(int i = 0; i < (int)adj[u].size(); i++) {
        int v, w; tie(v, w) = adj[u][i];
        h[v] = h[u] + 1;
        d[v] = (d[u] ^ w);
        dfs(v);
    }
    tout[u] = timer;
}

void insert(int value, int jikan) {
    node *current = root;
    for(int i = 30; i >= 0; i--) {
        int ch = ((value >> i) & 1);
        if(current -> children[ch] == nullptr) {
            current -> children[ch] = new node();
        }
        current = current -> children[ch];
        current -> jikan.insert(jikan);
    }
}

bool in(node *current, int l, int r) {
    auto it = current->jikan.lower_bound(l);
    if(it == current->jikan.end() || *it > r) return false;
    else return true;
}

int get(int value, int l, int r) {
    int ans = 0;
    node *current = root;
    for(int i = 30; i >= 0; i--) {
        int ch = ((value >> i) & 1);
        if(current -> children[1 - ch] != nullptr && in(current -> children[1 - ch], l, r)) {
            ans += (1 << i);
            current = current -> children[1 - ch];
        }else {
            current = current -> children[ch];
        }
    }
    return ans;
}

void process() {
    dfs(1);

    insert(0, 1);
    for(int i = 1; i <= q; i++) {
        string type; int a, b; tie(type, a, b) = queries[i];
        if(type[0] == 'A') insert(d[child[i]], tin[child[i]]);
        else cout << get(d[a], tin[b], tout[b]) << endl;
    }
}

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

    #define task "kurumi"
    if(fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    prepare();

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int32_t main()':
klasika.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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