oj.uz

Submission #199896

# Submission time Handle Problem Language Result Execution time Memory
199896 2020-02-03T22:56:28 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 839 ms 97876 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[4000006][4],tim[9000006][4],ans;
int en[200005],ot[200005],tmm;
vector<int>gr[200005],aq,bq;
vector<string>sq;
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 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];
    }
}
void qu(string s,int z,int x)
{
    if(s[z]=='1')
    {
        if(trie[x][0]!=0)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][0]);
        }
        else if(trie[x][1]!=0)
        {
            ans*=2;
            qu(s,z+1,trie[x][1]);
        }
    }
    else
    {
        if(trie[x][1]!=0)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][1]);
        }
        else if(trie[x][0]!=0)
        {
            ans*=2;
            qu(s,z+1,trie[x][0]);
        }
    }
}
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);
    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);
        }
        else
        {
            ans=0;
            long long b=a[x];
            qu(to(b),0,0);
            cout<<ans<<endl;
        }
    }
}

Compilation message

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:11: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)':
klasika.cpp:34: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 9 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 39316 KB Output is correct
2 Correct 773 ms 59304 KB Output is correct
3 Correct 634 ms 78456 KB Output is correct
4 Correct 514 ms 97876 KB Output is correct
5 Correct 808 ms 37132 KB Output is correct
6 Correct 749 ms 54808 KB Output is correct
7 Correct 649 ms 71452 KB Output is correct
8 Correct 546 ms 88104 KB Output is correct
9 Correct 839 ms 37524 KB Output is correct
10 Correct 723 ms 55572 KB Output is correct
11 Correct 636 ms 72944 KB Output is correct
12 Correct 518 ms 89780 KB Output is correct

Subtask #4
0 / 44.0

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