| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199892 |
2020-02-03T22:52:18 Z |
mdn2002 |
Klasika (COCI20_klasika) |
C++14 |
|
293 ms |
524292 KB |
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[200005],k,trie[3000006][3],ans;
int en[200005],ot[200005],tmm;
vector<int>gr[200005],aq,bq;
vector<string>sq;
set<int>tim[12000006];
void dfs(int x,int p)
{
en[x]=++tmm;
for(int i=0; i<gr[x].size(); i++)
{
int u=gr[x][i];
if(u==p)continue;
dfs(u,x);
}
ot[x]=tmm;
}
string to(long long x)
{
string s;
while(x)
{
s.push_back('0'+(x%2));
x/=2;
}
while(s.size()!=32)s.push_back('0');
reverse(s.begin(),s.end());
return s;
}
void ad(string s,int st)
{
int nod=0;
for(int i=0; i<s.size(); i++)
{
int x=s[i]-'0';
if(trie[nod][x]==0)trie[nod][x]=++k;
nod=trie[nod][x];
tim[nod].insert(st);
}
}
void qu(string s,int z,int x,int st,int fn)
{
if(s[z]=='1')
{
int tx1=trie[x][1];
int to1=1e9;
if(tim[tx1].lower_bound(st)!=tim[tx1].end())to1=*tim[tx1].lower_bound(st);
int txo=trie[x][0];
int too=1e9;
if(tim[txo].lower_bound(st)!=tim[txo].end())too=*tim[txo].lower_bound(st);
if(trie[x][0]!=0&&st<=too&&too<=fn)
{
ans*=2;
ans++;
qu(s,z+1,trie[x][0],st,fn);
return;
}
else if(trie[x][1]!=0&&st<=to1&&to1<=fn)
{
ans*=2;
qu(s,z+1,trie[x][1],st,fn);
}
}
else
{
int tx1=trie[x][1];
int to1=1e9;
if(tim[tx1].lower_bound(st)!=tim[tx1].end())to1=*tim[tx1].lower_bound(st);
int txo=trie[x][0];
int too=1e9;
if(tim[txo].lower_bound(st)!=tim[txo].end())too=*tim[txo].lower_bound(st);
if(trie[x][1]!=0&&st<=to1&&to1<=fn)
{
ans*=2;
ans++;
qu(s,z+1,trie[x][1],st,fn);
return;
}
else if(trie[x][0]!=0&&st<=too&&too<=fn)
{
ans*=2;
qu(s,z+1,trie[x][0],st,fn);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("gpsduel.in","r",stdin);
//freopen("gpsduel.out","w",stdout);
cin>>n;
int num=1;
for(int i=0; i<n; i++)
{
string s;
long long x,y;
cin>>s>>x>>y;
sq.push_back(s);
aq.push_back(x);
bq.push_back(y);
if(s=="Add")
{
num++;
gr[x].push_back(num);
}
}
dfs(1,0);
num=1;
string ss=to(0);
ad(ss,1);
for(int i=0; i<n; i++)
{
string s=sq[i];
long long x=aq[i],y=bq[i];
if(s=="Add")
{
num++;
a[num]=a[x]^y;
string st=to(a[num]);
ad(st,en[num]);
}
else
{
ans=0;
long long b=a[x];
qu(to(b),0,0,en[y],ot[y]);
cout<<ans<<endl;
}
}
}
Compilation message
klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gr[x].size(); i++)
~^~~~~~~~~~~~~
klasika.cpp: In function 'void ad(std::__cxx11::string, int)':
klasika.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<s.size(); i++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
293 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
293 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
278 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
293 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
