| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199561 |
2020-02-02T03:22:47 Z |
SamAnd |
Klasika (COCI20_klasika) |
C++17 |
|
5000 ms |
347500 KB |
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005;
int n, m;
pair<int, int> b[N];
vector<int> a[N];
int d[N];
int ti, tin[N], tout[N];
void dfs(int x)
{
tin[x] = ++ti;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
dfs(h);
}
tout[x] = ti;
}
int z[N * 4];
vector<vector<int> > t[N * 4];
void bil(int tl, int tr, int pos)
{
t[pos].push_back({0, 0});
if (tl == tr)
return;
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
}
void ubd(int tl, int tr, int x, int y, int pos)
{
int bpos = 0;
for (int i = 30; i >= 0; --i)
{
int u;
if (!(y & (1 << i)))
u = 0;
else
u = 1;
if (!t[pos][bpos][u])
{
t[pos][bpos][u] = ++z[pos];
t[pos].push_back({0, 0});
}
bpos = t[pos][bpos][u];
}
if (tl == tr)
return;
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
}
int qry(int tl, int tr, int l, int r, int y, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
{
int bpos = 0;
int ans = 0;
if (z[pos] == 0)
return ans;
for (int i = 30; i >= 0; --i)
{
int u;
if (!(y & (1 << i)))
u = 0;
else
u = 1;
if (t[pos][bpos][(u ^ 1)])
{
ans += (1 << i);
bpos = t[pos][bpos][(u ^ 1)];
}
else
{
bpos = t[pos][bpos][u];
}
}
return ans;
}
int m = (tl + tr) / 2;
return max(qry(tl, m, l, min(m, r), y, pos * 2),
qry(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1));
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &m);
n = 1;
for (int i = 1; i <= m; ++i)
{
char ty[10];
scanf(" %s", ty);
if (ty[0] == 'A')
{
int x, y;
scanf("%d%d", &x, &y);
++n;
a[x].push_back(n);
d[n] = (d[x] ^ y);
b[i] = m_p(n, -1);
}
else
{
int x, y;
scanf("%d%d", &x, &y);
b[i] = m_p(x, y);
}
}
dfs(1);
bil(1, n, 1);
for (int i = 1; i <= m; ++i)
{
if (b[i].second == -1)
{
int x = b[i].first;
ubd(1, n, tin[x], d[x], 1);
}
else
{
int x = b[i].first;
int y = b[i].second;
printf("%d\n", qry(1, n, tin[y], tout[y], d[x], 1));
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
klasika.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", ty);
~~~~~^~~~~~~~~~~
klasika.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
klasika.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
24696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
24696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5483 ms |
347500 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
24696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
