oj.uz

Submission #199872

# Submission time Handle Problem Language Result Execution time Memory
199872 2020-02-03T22:18:36 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 845 ms 97492 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<<max(b,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 827 ms 39060 KB Output is correct
2 Correct 765 ms 59236 KB Output is correct
3 Correct 646 ms 78376 KB Output is correct
4 Correct 504 ms 97492 KB Output is correct
5 Correct 845 ms 37132 KB Output is correct
6 Correct 729 ms 54804 KB Output is correct
7 Correct 655 ms 71600 KB Output is correct
8 Correct 554 ms 88016 KB Output is correct
9 Correct 831 ms 37396 KB Output is correct
10 Correct 754 ms 55444 KB Output is correct
11 Correct 617 ms 72996 KB Output is correct
12 Correct 500 ms 89652 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 -