oj.uz

Submission #199873

# Submission time Handle Problem Language Result Execution time Memory
199873 2020-02-03T22:19:07 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 869 ms 97624 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[6000006][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 850 ms 39188 KB Output is correct
2 Correct 759 ms 59088 KB Output is correct
3 Correct 656 ms 78656 KB Output is correct
4 Correct 526 ms 97624 KB Output is correct
5 Correct 869 ms 37008 KB Output is correct
6 Correct 826 ms 55060 KB Output is correct
7 Correct 671 ms 71580 KB Output is correct
8 Correct 545 ms 87848 KB Output is correct
9 Correct 822 ms 37412 KB Output is correct
10 Correct 716 ms 55572 KB Output is correct
11 Correct 628 ms 73160 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 -