oj.uz

Submission #199868

# Submission time Handle Problem Language Result Execution time Memory
199868 2020-02-03T22:15:22 Z mdn2002 Klasika (COCI20_klasika) C++14
0 / 110
 2570 ms 524296 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[5000006][4],ans;
int en[200005],ot[200005],tmm;
vector<int>gr[200005],aq,bq;
vector<string>sq;
set<int>tim[9000006];
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 tx=trie[x][0];
        int to=1e9;
        if(tim[tx].lower_bound(st)!=tim[tx].end())to=*tim[tx].lower_bound(st);
        if(trie[x][0]!=0&&st<=to&&to<=fn)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][0],st,fn);
            return;
        }
        tx=trie[x][1];
        to=1e9;
        if(tim[tx].lower_bound(st)!=tim[tx].end())to=*tim[tx].lower_bound(st);
        if(trie[x][1]!=0&&st<=to&&to<=fn)
        {
            ans*=2;
            qu(s,z+1,trie[x][1],st,fn);
        }
    }
    else
    {
        int tx=trie[x][1];
        int to=1e9;
        if(tim[tx].lower_bound(st)!=tim[tx].end())to=*tim[tx].lower_bound(st);
        if(trie[x][1]!=0&&st<=to&&to<=fn)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][1],st,fn);
            return;
        }
        tx=trie[x][0];
        to=1e9;
        if(tim[tx].lower_bound(st)!=tim[tx].end())to=*tim[tx].lower_bound(st);
        if(trie[x][0]!=0&&st<=to&&to<=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;
    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,1,1e9);
            cout<<max(b,ans)<<endl;
        }
    }
}

Compilation message

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:12:18: 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:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++)
                 ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 427896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 427896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2570 ms 520728 KB Output is correct
2 Runtime error 1428 ms 524296 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 427896 KB Output isn't correct
2 Halted 0 ms 0 KB -