| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 201076 |
2020-02-09T09:38:32 Z |
mraron |
Klasika (COCI20_klasika) |
C++14 |
|
1501 ms |
239980 KB |
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=3.1415926535897932384626433832795;
const ll INF = 1LL<<62;
const ll MINF = -1LL<<62;
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)
int q;
struct op {
int typ,a,b;
};
int n=1;
vector<op> lst;
vector<pair<int,int>> adj[200001];
int sz[200001], par[200001], d[200001];
void dfs_pre(int x) {
sz[x]=1;
for(auto i:adj[x]) {
if(!sz[i.xx]) {
par[i.xx]=x;
d[i.xx]=i.yy^d[x];
dfs_pre(i.xx);
sz[x]+=sz[i.xx];
}
}
}
int hld_top[200001], hld_id[200001], hld_pos[2000001], pos=0, id=1;
void dfs_hld(int x) {
// cerr<<x<<" "<<pos<<"\n";
hld_id[x]=id;
hld_pos[x]=pos++;
if(!hld_top[hld_id[x]]) {
hld_top[hld_id[x]]=x;
}
int best=0;
for(auto i:adj[x]) {
if(par[x]==i.xx) continue ;
if(!best || sz[best]<sz[i.xx]) best=i.xx;
}
if(best>0) dfs_hld(best);
for(auto i:adj[x]) {
if(par[x]!=i.xx && i.xx!=best) {
id++;
dfs_hld(i.xx);
}
}
}
struct node {
node* sub[2];
node() {
sub[0]=sub[1]=NULL;
}
};
void insert(node* root, int num) {
for(int i=30;i>=0;i--) {
int c=(num&(1<<i))!=0;
if(root->sub[c]==NULL) {
root->sub[c]=new node;
}
root=root->sub[c];
}
}
int mx(node *root, int with) {
if(root==NULL) return 0;
if(root->sub[0]==NULL && root->sub[1]==NULL) return 0;
int ans=0;
for(int i=30;i>=0;i--) {
int c=(with&(1<<i))!=0;
if(root->sub[1-c]!=NULL) {
ans|=1<<i;
root=root->sub[1-c];
}else {
root=root->sub[c];
}
}
return ans;
}
node* tree[4*400001];
void add(int ind, int L, int R, int i, int j, int mit) {
//cerr<<ind<<" "<<L<<" "<<R<<" "<<i<<" "<<j<<" "<<mit<<"add\n"<<flush;
if(R<i || j<L) return ;
if(i<=L && R<=j) {
if(tree[ind]==NULL) tree[ind]=new node;
insert(tree[ind], mit);
return ;
}
add(2*ind, L, (L+R)/2, i, j, mit);
add(2*ind+1, (L+R)/2+1, R, i, j, mit);
}
int mx(int ind, int L, int R, int i, int with) {
//cerr<<ind<<" "<<L<<" "<<R<<" "<<i<<" "<<i<<" "<<with<<"mx\n"<<flush;
if(R<i || i<L) return 0;
int ans=0;
if(L<=i && i<=R) ans=mx(tree[ind], with);
if(L!=R) ans=max(ans, max(mx(2*ind, L, (L+R)/2, i, with), mx(2*ind+1, (L+R)/2+1, R, i, with)));
return ans;
}
void add(int root, int dd) {
while(root>0) {
int blk=hld_id[root];
int tp=hld_top[blk];
add(1,0,pos-1,hld_pos[tp],hld_pos[root],dd);
root=par[tp];
}
}
int query(int a, int b) {
int base=d[a];
//cerr<<base<<"\n";
//cerr<<hld_pos[b]<<"\n";
return mx(1,0,pos-1,hld_pos[b],base);
}
int main() {
IO;
cin>>q;
lst.resize(q);
for(int i=0;i<q;++i) {
string t;
cin>>t;
lst[i].typ=(t=="Add"?0:1);
cin>>lst[i].a>>lst[i].b;
if(lst[i].typ==0) {
adj[lst[i].a].push_back({n+1, lst[i].b});
adj[n+1].push_back({lst[i].a, lst[i].b});
lst[i].a=n+1;
n++;
}
}
dfs_pre(1);
dfs_hld(1);
for(auto i:lst) {
if(i.typ==0) {
//cerr<<"typ0\n";
add(i.a, d[i.a]);
}else {
//cerr<<"typ1\n";
cout<<query(i.a,i.b)<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1501 ms |
239980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
