제출 #1281958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281958		aren_dance	Klasika (COCI20_klasika)	C++20	33 / 110	1935 ms	121080 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<unordered_set<int>> t(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[i].find(cnt) == t[i].end()) {
				t[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[i].find(cnt) == t[i].end()) {
			t[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[i].find(d) != t[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: 33 / 33
• Subtask 4: 0 / 44