| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1116358 |
2024-11-21T14:25:27 Z |
8pete8 |
Klasika (COCI20_klasika) |
C++17 |
|
1110 ms |
71904 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mxn=2e5+5,lg=29,inf=1e9,minf=-1e9;
int n,q;
vector<pair<int,pii>>qry;
vector<pii>adj[mxn+10];
int tin[mxn+10],tout[mxn+10],T=0,dist[mxn+10];
void dfs(int cur,int p){
tin[cur]=++T;
for(auto i:adj[cur])if(i.f!=p){
dist[i.f]=dist[cur]^i.s;
dfs(i.f,cur);
}
tout[cur]=T;
}
struct mst{
set<int>v[2*mxn+10];
void update(int pos,int val){
pos+=n;
v[pos].insert(val);
for(int i=pos;i>0;i>>=1)v[i>>1].insert(val);
}
int check(int pos,int x,int y){
auto it=v[pos].lb(x);
if(it==v[pos].end())return 0;
return (*it)<=y;
}
int qry(int l,int r,int x,int y){
int have=0;
for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
if(l&1)have|=check(l++,x,y);
if(!(r&1))have|=check(r--,x,y);
}
return have;
}
}t;
int32_t main(){
fastio
cin>>q;
n=1;
for(int i=0;i<q;i++){
string a;cin>>a;
int x,y;cin>>x>>y;
if(a[0]=='A'){
n++;
qry.pb({1,{n,y}});
adj[n].pb({x,y});
adj[x].pb({n,y});
}
else qry.pb({0,{x,y}});
}
dfs(1,-1);
for(int i=0;i<q;i++){
if(qry[i].f)t.update(tin[qry[i].s.f],dist[qry[i].s.f]);
else{
int cur=0;
for(int k=30;k>=0;k--){
if(!(dist[qry[i].s.f]&(1LL<<k))){
//trying to get 1
cur+=(1LL<<k);
if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur-=(1LL<<k);
}
else{
if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur+=(1LL<<k);
}
}
cout<<(dist[qry[i].s.f]^cur)<<'\n';
}
}
}
/*
basically given a value x
find a value y in rang [l,r] where x^y is minimum
try fixing bit
let say we fix suffix(most sig bit) to be XXX1001
and the X are not fix
the min value is 0001001 and max value is 1111001
to see if there exist a value with this suffix
just check if theres a value between 0001001 and 1111001
merge sort tree on euler tour?
each update = log^2(n)
qry =log^3(n)
x=add,y=qry
y=2e5-x;
xlog^2(x) + ylog^2(x)30
xlog^2(x)+(2e5-x)log^2(x)30
worst case x=33,300 y=1e8
should pass??
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
28460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
28460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1110 ms |
71904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
28460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
