Submission #1114280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114280		ljtunas	Klasika (COCI20_klasika)	C++14	110 / 110	2490 ms	442076 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define all(h) h.begin(), h.end()
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 2e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

// (x, y) -> (u, v) = Ckn(u - x, x + y - u - v);
// Ckn(k, a) * Ckn(k, b) = C(a, a + b);  (k : 1 -> min(a, b))

void fixmod(int &val) {
    if (val < 0) val += MOD*MOD;
    val %= MOD;
}
int n = 1, q, f[MAXN], num[MAXN], tail[MAXN];
vii g[MAXN];

struct Query{
	int x, y, type;
}; vector<Query> Q;

void dfs_init(int u, int par, int val) {
	static int time_dfs = 0;
	num[u] = ++time_dfs;
	f[u] = val;
	Forv(tmp, g[u]) {
		if (tmp.fi == par) continue;
		dfs_init(tmp.fi, u, val ^ tmp.se);
	}
	tail[u] = time_dfs;
}

struct node {
	set<int> s;
    node *child[2];
    node() {
        child[0] = child[1] = nullptr;
    }
};

struct Trie{
    node *root = new node();
    void add(int x, int id) {
        node *r = root;
        Ford(bit, 30, -1) {
        	r -> s.insert(id);
        	if (bit < 0) break;
            int k = Bit(x, bit);
            if (r -> child[k] == nullptr)
                r -> child[k] = new node;
            r = r -> child[k];
        }
    }
    int get(int x, int in, int en) {
    	node *r = root;
    	int res = 0;
    	Ford(bit, 30, -1) {
    		if (bit < 0) break;
    		int k = Bit(x, bit);
    		if (r->child[!k]==nullptr||r->child[!k]->s.lower_bound(in)==r->child[!k]->s.upper_bound(en)){
    			r = r->child[k];
    		} else {
    			res += (1<<bit);
    			r=r->child[!k];
    		}
    	}
    	return res;
    }
} Trie;

void Progess() {
	cin >> q;
	while (q--) {
		int x, y;
		string s; cin >> s >> x >> y;
		if (s == "Add") {
			++n;
			Q.emplace_back(Query{n, y, 1});
			g[x].emplace_back(ii{n, y});
			g[n].emplace_back(ii{x, y});
		} else {
			Q.emplace_back(Query{x, y, 0});
		}
	}
	dfs_init(1, 0, 0);
	Trie.add(0, 1);
	Forv(tmp, Q) {
		if (tmp.type == 1) {
			Trie.add(f[tmp.x], num[tmp.x]);
		} else {
			cout << Trie.get(f[tmp.x], num[tmp.y], tail[tmp.y]) << '\n';
		}
	}
}

signed main(void) {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cout.tie(nullptr);

    #define task "main"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }//_______________________________
    Progess();
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

klasika.cpp:32:23: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   32 | const int   oo = 1e18 + 1;
      |                  ~~~~~^~~
klasika.cpp: In function 'void fixmod(int&)':
klasika.cpp:49:28: warning: integer overflow in expression of type 'int' results in '-371520463' [-Woverflow]
   49 |     if (val < 0) val += MOD*MOD;
      |                         ~~~^~~~
klasika.cpp: In function 'int main()':
klasika.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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