oj.uz

Submission #199899

# Submission time Handle Problem Language Result Execution time Memory
199899 2020-02-03T22:57:47 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 846 ms 97532 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[2600006][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 8 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 8 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 843 ms 38932 KB Output is correct
2 Correct 730 ms 59048 KB Output is correct
3 Correct 622 ms 78272 KB Output is correct
4 Correct 519 ms 97532 KB Output is correct
5 Correct 827 ms 37132 KB Output is correct
6 Correct 763 ms 55000 KB Output is correct
7 Correct 666 ms 71456 KB Output is correct
8 Correct 537 ms 87848 KB Output is correct
9 Correct 846 ms 37396 KB Output is correct
10 Correct 731 ms 55532 KB Output is correct
11 Correct 626 ms 73000 KB Output is correct
12 Correct 513 ms 89780 KB Output is correct

Subtask #4
0 / 44.0

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