Submission #868788

#TimeUsernameProblemLanguageResultExecution timeMemory
868788PringKlasika (COCI20_klasika)C++14
0 / 110
5060 ms604 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...