| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 868788 |
2023-11-02T02:25:46 Z |
Pring |
Klasika (COCI20_klasika) |
C++14 |
|
5000 ms |
604 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<pii, int> p3i;
const int MXN = 2005;
int n, now = 1, pw[MXN], x[MXN], y[MXN];
vector<pii> edge[MXN];
vector<int> ans;
bitset<MXN> ban;
string s;
int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C = 1;
struct BIT {
int n, val[MXN];
void init(int _n) {
n = _n;
fill(val + 1, val + n + 1, 0);
}
void modify(int id, int x) {
for (; id <= n; id += (id & -id)) val[id] ^= x;
}
int query(int id) {
int ans = 0;
for (; id > 0; id -= (id & -id)) ans ^= val[id];
return ans;
}
int query(int l, int r) {
return query(r) ^ query(l - 1);
}
void COUT() {
for (int i = 1; i <= n; i++) cout << val[i] << ' ';
cout << endl;
}
} B;
void DFS1(int id, int parent, int depth) {
p[id] = parent;
d[id] = depth;
sz[id] = 1;
son[id] = -1;
for (auto &i : edge[id]) {
if (i.sc == parent) continue;
DFS1(i.sc, id, depth + 1);
sz[id] += sz[i.sc];
if (son[id] == -1) son[id] = i.sc;
else if (sz[son[id]] < sz[i.sc]) son[id] = i.sc;
}
// cout << id << ' ' << son[id] << endl;
}
void DFS2(int id, int parent, int _top) {
// cout << "DFS2 " << id << ' ' << son[id] << endl;
top[id] = _top;
dfn[id] = C++;
if (son[id] != -1) DFS2(son[id], id, _top);
for (auto &i : edge[id]) {
if (i.sc == parent) continue;
if (i.sc == son[id]) continue;
DFS2(i.sc, id, i.sc);
}
}
void BUILD() {
B.init(now);
for (int i = 2; i <= now; i++) B.modify(dfn[i], pw[i]);
// B.COUT();
}
void DFS(int id, int parent, int acc, vector<int> &v) {
if (ban[id]) return;
v.push_back(acc);
for (auto &i : edge[id]) {
if (i.sc == parent) continue;
DFS(i.sc, id, acc ^ i.fs, v);
}
}
inline int CLIMB(int x, int y) {
int ans = 0;
if (d[x] < d[y]) swap(x, y);
while (top[x] != top[y]) {
ans ^= B.query(dfn[top[x]], dfn[x]);
x = p[top[x]];
if (d[x] < d[y]) swap(x, y);
}
ans ^= B.query(dfn[top[y]] + 1, dfn[x]);
return ans;
}
inline int calc(int x, int y) {
// cout << "calc " << x << ' ' << y << endl;
vector<int> v;
DFS(y, p[y], 0, v);
int xxx = CLIMB(x, y), ans = 0;
// cout << xxx << endl;
for (auto &i : v) ans = max(ans, xxx ^ i);
return ans;
}
void miku() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s >> x[i] >> y[i];
if (s[0] == 'A') {
now++;
edge[now].push_back(mp(y[i], x[i]));
edge[x[i]].push_back(mp(y[i], now));
pw[now] = y[i];
} else {
y[i] *= -1;
}
}
// for (int i = 1; i <= now; i++) {
// for (auto &j : edge[i]) cout << i << ' ' << j.sc << endl;
// }
DFS1(1, 0, 0);
DFS2(1, 0, 1);
// cout << "PRING" << endl;
// for (int i = 1; i <= now; i++) cout << dfn[i] << ' ';
// cout << endl;
BUILD();
for (int i = n - 1; i >= 0; i--) {
if (y[i] > 0) {
B.modify(dfn[now], pw[now]);
ban[now] = true;
now--;
// B.COUT();
} else {
y[i] *= -1;
// cout << calc(x[i], y[i]) << endl;
ans.push_back(calc(x[i], y[i]));
}
}
reverse(ans.begin(), ans.end());
for (auto &i : ans) cout << i << endl;
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
miku();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
