| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1118716 | vjudge1 | Klasika (COCI20_klasika) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define TASK ""
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
mt19937 rng(time(0));
const int N = (int)2e5 + 7;
int q;
vector<int> adj[N];
int n = 1;
int f[N];
void Read()
{
cin >> q;
}
namespace Subtask2
{
bool Check()
{
return q <= 2000;
}
string type;
int a, b;
int ans = 0;
void DFS(int u)
{
maximize(ans, f[a] ^ f[u]);
for(int v : adj[u])
{
DFS(v);
}
}
void Solve()
{
REP(i, q)
{
cin >> type >> a >> b;
if(type[0] == 'A')
{
++n;
adj[a].push_back(n);
f[n] = f[a] ^ b;
}
else
{
ans = 0;
DFS(b);
cout << ans << '\n';
}
}
}
}
namespace Subtask3
{
#define int long long
int child[30 * N][2], sz = 0;
// bool isEnd[100];
string type;
int a, b;
void Ins(int mask)
{
int u = 0;
FORD(i, 31, 0)
{
int val = mask >> i & 1;
if(!child[u][val])
{
child[u][val] = ++sz;
u = sz;
}
else
u = child[u][val];
}
}
int Ask(int mask)
{
int u = 0, res = 0;
FORD(i, 31, 0)
{
int val = mask >> i & 1;
val ^= 1;
if(child[u][val])
{
u = child[u][val];
res += (1 << i);
}
else
{
u = child[u][val ^ 1];
}
}
return res;
}
void Solve()
{
REP(i, q)
{
cin >> type >> a >> b;
if(type[0] == 'A')
{
++n;
f[n] = f[a] ^ b;
Ins(f[n]);
}
else
{
cout << Ask(f[a]) << '\n';
}
}
}
}
void Solve()
{
if(Subtask2::Check()) return Subtask2::Solve();
return Subtask3::Solve();
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
if(fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
Read();
Solve();
return 0;
}
/*
5
Add 1 8
Add 2 7
Add 1 4
Add 4 3
Query 3 1
*/
#include <bits/stdc++.h>
using namespace std;
#define TASK ""
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
mt19937 rng(time(0));
const int N = (int)2e5 + 7;
int q;
vector<int> adj[N];
int n = 1;
int f[N];
void Read()
{
cin >> q;
}
namespace Subtask2
{
bool Check()
{
return q <= 2000;
}
string type;
int a, b;
int ans = 0;
void DFS(int u)
{
maximize(ans, f[a] ^ f[u]);
for(int v : adj[u])
{
DFS(v);
}
}
void Solve()
{
REP(i, q)
{
cin >> type >> a >> b;
if(type[0] == 'A')
{
++n;
adj[a].push_back(n);
f[n] = f[a] ^ b;
}
else
{
ans = 0;
DFS(b);
cout << ans << '\n';
}
}
}
}
namespace Subtask3
{
#define int long long
int child[30 * N][2], sz = 0;
// bool isEnd[100];
string type;
int a, b;
void Ins(int mask)
{
int u = 0;
FORD(i, 31, 0)
{
int val = mask >> i & 1;
if(!child[u][val])
{
child[u][val] = ++sz;
u = sz;
}
else
u = child[u][val];
}
}
int Ask(int mask)
{
int u = 0, res = 0;
FORD(i, 31, 0)
{
int val = mask >> i & 1;
val ^= 1;
if(child[u][val])
{
u = child[u][val];
res += (1 << i);
}
else
{
u = child[u][val ^ 1];
}
}
return res;
}
void Solve()
{
REP(i, q)
{
cin >> type >> a >> b;
if(type[0] == 'A')
{
++n;
f[n] = f[a] ^ b;
Ins(f[n]);
}
else
{
cout << Ask(f[a]) << '\n';
}
}
}
}
void Solve()
{
if(Subtask2::Check()) return Subtask2::Solve();
return Subtask3::Solve();
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
if(fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
Read();
Solve();
return 0;
}
/*
5
Add 1 8
Add 2 7
Add 1 4
Add 4 3
Query 3 1
*/