| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1110356 |
2024-11-09T10:03:43 Z |
FucKanh |
Klasika (COCI20_klasika) |
C++14 |
|
715 ms |
524288 KB |
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
#define p3i pair<int,pii>
#define p4i pair<pii,pii>
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 2;
int h[maxn],ans[maxn];
vector<p3i> a[maxn];
vector<p4i> qr[maxn];
struct node {
int u,pa,jump,len,vpa,vjump;
node() {};
node(int u) : u(u) {}
node(int u, int pa, int jump, int len, int vpa,int vjump) : u(u), pa(pa), jump(jump), len(len), vpa(vpa), vjump(vjump) {}
};
node info[maxn];
void add(int u,int pa,int w) {
h[u] = h[pa] + 1;
int len,jump,vpa = w,vjump;
if (info[pa].len == info[info[pa].jump].len) {
len = info[pa].len * 2 + 1;
jump = info[info[pa].jump].jump;
vjump = w ^ info[pa].vjump ^ info[info[pa].jump].vjump;
}
else {
len = 1;
jump = pa;
vjump = w;
}
info[u] = node(u,pa,jump,len,vpa,vjump);
}
pii binlift(int u, int k) {
int des = h[u] - k;
int value = 0;
while (h[u] != des) {
// cerr << u << " " << h[u] << " " << des << endl;
// system("pause");
if (h[info[u].jump] < des) {
value ^= info[u].vpa;
u = info[u].pa;
}
else {
value ^= info[u].vjump;
u = info[u].jump;
}
}
return {u,value};
}
int LCA(int u, int v) {
if (h[u] > h[v]) swap(u,v);
pii tmp = binlift(v,h[v]-h[u]);
int val = 0;
v = tmp.first;
// cerr << u << " " << v << endl;
while (u != v) {
if (info[u].jump != info[v].jump) {
val ^= info[u].vjump ^ info[v].vjump;
u = info[u].jump;
v = info[v].jump;
}
else {
val ^= info[u].vpa ^ info[v].vpa;
u = info[u].pa;
v = info[v].pa;
}
}
// cerr << val << " " << tmp.second << endl;
return val ^ tmp.second;
}
struct nodetrie {
int la, t[2];
nodetrie *p[2];
nodetrie() {
t[0] = t[1] = 0;
p[0] = p[1] = nullptr;
la = 0;
}
nodetrie(nodetrie *l, nodetrie *r, int tl, int tr) {
t[0] = (tl);
t[1] = (tr);
p[0] = (l);
p[1] = (r);
la = 0;
}
};
void push(nodetrie *p,int pos) {
if (p->la) {
for (int i = 0; i < 2; i++) {
if (p->p[i]!=nullptr) p->p[i]->la ^= p->la;
}
if (p->la & (1<<pos-1)) {
swap(p->p[0],p->p[1]), swap(p->t[0],p->t[1]);
}
p->la=0;
}
}
class trie {
public:
int sz;
nodetrie *root = new nodetrie();
void update(nodetrie *p, int pos, int val, int t) {
// cerr << "update: "<< pos << endl;
if (pos==0) return;
push(p,pos);
int bit = (val&(1<<pos-1))!=0;
if (p->p[bit]==nullptr){
p->t[bit] = t;
p->p[bit] = new nodetrie();
}
else {
p->t[bit] = min(t,p->t[bit]);
}
update( p->p[bit], pos - 1, val, t);
}
int get(nodetrie *p, int pos, int val, int t) {
if (pos==0) return 0;
// cerr<< pos << " " << t << endl;
assert(p!=nullptr);
push(p,pos);
int bit = (val&(1<<pos-1))!=0;
// cerr<< pos << " " << t << " " << bit << endl;
if (p->p[bit]==nullptr || p->t[bit] > t){
// cerr << "Ok" << endl;
return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1);
}
else {
// cerr << "xam" << endl;
return get(p->p[bit],pos-1,val,t) | (bit << pos-1);
}
}
int get(int val, int t) {
return get(root,31,val,t);
}
void update(int val, int t) {
update(root,31,val,t);
sz++;
}
void addlazy(int val) {
root->la ^= val;
}
void init(int t) {
// cerr << "init: " << t << endl;
update(root,31,0,t);
sz = 0;
}
void print(nodetrie *p, int pos, int val, int t) {
// if (pos <= 5) cerr << "> " << pos << " " << (p->la) << " | " << p->la << endl;
push(p,pos);
if (pos==0) {
cerr << ">> " << val << " "<< t<< endl; return;
}
for (int i = 0; i < 2; i++) {
if (p->p[i] == nullptr) continue;
print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i]));
}
}
void print(int u) {
cerr << "tree print: " << u << endl;
print(root,31,0,0);
}
};
void merged(nodetrie *a, nodetrie *b, int pos) {
if (pos==0) return;
push(a,pos);
push(b,pos);
// cerr << "merge: " << pos << endl;
for (int i = 0; i < 2; i++) {
if (b->p[i] == nullptr) continue;
if (a->p[i] == nullptr) {
a->p[i] = new nodetrie();
a->t[i] = b->t[i];
}
else {
a->t[i] = min(a->t[i], b->t[i]);
}
merged(a->p[i], b->p[i], pos - 1);
}
}
trie tree[maxn];
void dfs(int u) {
// cerr <<"vst u:" << u << endl;
if (a[u].empty()) {
// tree[u].print(u);
for (p4i val : qr[u]) {
int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se;
int ori = LCA(x,y);
ans[idx] = tree[u].get(~ori,t);
}
return;
}
for (p3i tmp : a[u]) {
int w,v;
w = tmp.se.fi;
v = tmp.fi;
tree[v].init(tmp.se.se);
dfs(v);
tree[v].addlazy(w);
if (tree[u].sz < tree[v].sz) swap(tree[u], tree[v]);
merged(tree[u].root, tree[v].root, 31);
}
// tree[u].print(u);
for (p4i val : qr[u]) {
int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se;
int ori = LCA(x,y);
// cerr << ori << " : " << t << endl;
ans[idx] = ori ^ tree[u].get(~ori,t);
}
}
void solve() {
int q; cin >> q;
int cnt = 1, cntqr=0, t = 0;
info[1] = node(1,0,0,-1,0,0);
for (int i = 1; i <= q; i++) {
string s;cin >> s;
t++;
if (s=="Add") {
int x,w; cin >> x >> w;
add(++cnt,x,w);
a[x].push_back({cnt,{w,t}});
}
else {
int x,y; cin >> x >> y;
qr[y].push_back({{x,y},{++cntqr,t}});
}
}
tree[1].init(0);
dfs(1);
for (int i = 1; i <= cntqr; i++) {
cout << ans[i] << '\n';
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
Compilation message
klasika.cpp: In function 'void push(nodetrie*, long long int)':
klasika.cpp:105:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
105 | if (p->la & (1<<pos-1)) {
| ~~~^~
klasika.cpp: In member function 'void trie::update(nodetrie*, long long int, long long int, long long int)':
klasika.cpp:120:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
120 | int bit = (val&(1<<pos-1))!=0;
| ~~~^~
klasika.cpp: In member function 'long long int trie::get(nodetrie*, long long int, long long int, long long int)':
klasika.cpp:136:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
136 | int bit = (val&(1<<pos-1))!=0;
| ~~~^~
klasika.cpp:140:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
140 | return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1);
| ~~~^~
klasika.cpp:144:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
144 | return get(p->p[bit],pos-1,val,t) | (bit << pos-1);
| ~~~^~
klasika.cpp: In member function 'void trie::print(nodetrie*, long long int, long long int, long long int)':
klasika.cpp:175:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
175 | print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i]));
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25936 KB |
Output is correct |
| 2 |
Correct |
16 ms |
27728 KB |
Output is correct |
| 3 |
Correct |
23 ms |
32848 KB |
Output is correct |
| 4 |
Correct |
31 ms |
37960 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25936 KB |
Output is correct |
| 2 |
Correct |
16 ms |
27728 KB |
Output is correct |
| 3 |
Correct |
23 ms |
32848 KB |
Output is correct |
| 4 |
Correct |
31 ms |
37960 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
715 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25936 KB |
Output is correct |
| 2 |
Correct |
16 ms |
27728 KB |
Output is correct |
| 3 |
Correct |
23 ms |
32848 KB |
Output is correct |
| 4 |
Correct |
31 ms |
37960 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
