oj.uz

Submission #673999

# Submission time Handle Problem Language Result Execution time Memory
673999 2022-12-22T14:08:05 Z vjudge1 Klasika (COCI20_klasika) C++14
0 / 110
 224 ms 138132 KB 
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 200005;
set<int> se[N];
int numNode = 1;
int h[N], timer;
int n, nxt[N][31];
string op; int a, b;
int tin[N], tout[N];
vector<pair<int, int>> adj[N];
pair<string, pair<int, int>> q[N];

void dfs(int u) {
	tin[u] = ++timer;
	for (pair<int, int> x: adj[u]) {
		h[x.fi] = h[u] ^ x.se;
		dfs(x.fi);
	}
	tout[u] = timer;
}

int numNTrie = 0;

void add(int u) {
	int x = h[u], id = tin[u], p = 0;
	for (int i = 30; i >= 0; --i) {
		int LOVE = x >> i & 1;
		if (nxt[p][LOVE] == 0) nxt[p][LOVE] = ++numNTrie;
		p = nxt[p][LOVE]; se[p].insert(id);
	}
}

bool check(int p, int l, int r) {
	auto it = se[p].lower_bound(l);
	if (it == se[p].end()) return false;
	return *it <= r;
}

void query(int x, int l, int r) {
	int p = 0, ans = 0;
	for (int i = 30; i >= 0; --i) {
		int LOVE = (x >> i & 1) ^ 1;
		if (nxt[p][LOVE] == 0 || !check(nxt[p][LOVE], l, r)) LOVE ^= 1;
		p = nxt[p][LOVE]; ans += LOVE << i; 
	}
	cout << (x ^ ans) << '\n';
}

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

  	if (fopen(task".inp","r")) {
    	freopen(task".inp","r",stdin);
    	freopen(task".out","w",stdout);
  	}

	add(0);	
  	cin >> n;
  	numNode = 1;
  	for (int i = 0; i < n; ++i) {
  		cin >> op >> a >> b;
  		q[i] = {op, {a, b}};
  		if (op == "Add") 
  			adj[a].push_back({++numNode, b});
  	}
  	dfs(1);
  	numNode = 1;
  	for (int i = 0; i < n; ++i) {
  		if (q[i].fi == "Add") add(++numNode);
  		else query(h[q[i].se.fi], tin[q[i].se.se], tout[q[i].se.se]);
  	}
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:67:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:68:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22484 KB Output is correct
2 Incorrect 11 ms 22612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22484 KB Output is correct
2 Incorrect 11 ms 22612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 138132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22484 KB Output is correct
2 Incorrect 11 ms 22612 KB Output isn't correct
3 Halted 0 ms 0 KB -