Submission #1281979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281979		aren_dance	Klasika (COCI20_klasika)	C++20	0 / 110	261 ms	589824 KiB

klasika

// oj us strah.cpp : This file contains the 'main' function. Program execution begins and ends there.
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <complex>
#include <cassert>
#include <cfloat>
#include <memory>
#include <chrono>
#include <random>
#include <climits>
#include <limits>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <tuple>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
#define ll long long 
using namespace std;
const int N = 2e5+1;
ll tin[N];
ll tout[N];
vector<vector<unordered_set<int>>> t(2*N,vector<unordered_set<int>> (30));
vector<int> g[N];
ll a[2*N];
int tim;
int n;
void update(int v,int l,int r,int pos,int new_val) {
	if (l == r) {
		int cnt = 0;
		for (int i = 29;i >= 0;--i) {
			if (((1 << i) & new_val)) {
				cnt += (1 << i);
			}
			if (t[v][i].find(cnt) == t[v][i].end()){
				t[v][i].insert(cnt);
			}
		}
		return;
	}
	int m = (l + r) / 2;
	if (pos<=m) {
		update(2 * v, l, m, pos, new_val);
	}
	else {
		update(2 * v + 1, m + 1, r, pos, new_val);
	}
	int cnt = 0;
	for (int i = 29;i >= 0;--i) {
		if (((1 << i) & new_val)) {
			cnt += (1 << i);
		}
		if (t[v][i].find(cnt) == t[v][i].end()){
			t[v][i].insert(cnt);
	    }
	}
}
bool get(int v, int l, int r, int s, int e, int d,int i) {
	if (s > e) {
		return 0;
	}
	if (l == s && e == r) {
		if (t[v][i].find(d) != t[v][i].end()) {
			return 1;
		}
		return 0;
	}
	int m = (l + r) / 2;
	return (get(2 * v, l, m, s, min(e, m), d,i) | get(2 * v + 1, m + 1, r, max(m + 1, s), e, d,i));
}
void dfs(int v,int p) {
	tin[v] = ++tim;
	for (auto i : g[v]) {
		dfs(i, v);
	}
	tout[v] = ++tim;
}
int main()
{
	cin >> n;
	vector<vector<int>> mas(n+1);
	int gag = 1;
	for (int i = 1;i <= n;++i) {
		string s;int u, v;
		cin >> s >> u >> v;
		if (s[0] == 'A') {
			gag++;
			g[u].push_back(gag);
			a[gag] = a[u] ^ v;
			mas[i] = {0,gag,v};
		}
		else {
			mas[i] = {1,u,v};
		}
	}
	dfs(1, 0);
	update(1, 1, 2 * gag, tin[1], 0);
	for (int i = 1;i <= n;++i) {
		if (mas[i][0]) {
			int g = mas[i][1];
			int o = mas[i][2];
			int sum1 = 0;
			for (int j = 29;j >= 0;--j) {
				int v = (1<<j);
				if ((v&a[g])) {
					v = 0;
				}
				if (get(1, 1,2*gag,tin[o], tout[o], (sum1 + v),j)) {
					sum1 += v;
				}
				else {
					sum1 += ((1 << j) - v);
				}
			}
			cout << (sum1^a[g]) << '\n';
		}
		else {
			update(1,1,2*gag,tin[mas[i][1]], a[mas[i][1]]);
		}
	}
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

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