oj.uz

Submission #199881

# Submission time Handle Problem Language Result Execution time Memory
199881 2020-02-03T22:34:00 Z mdn2002 Klasika (COCI20_klasika) C++14
11 / 110
 344 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[6000006][4],ans;
int en[200005],ot[200005],tmm;
vector<int>gr[200005],aq,bq;
vector<string>sq;
set<int>tim[11000006];
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 tx1=trie[x][1];
        int to1=1e9;
        if(tim[tx1].lower_bound(st)!=tim[tx1].end())to1=*tim[tx1].lower_bound(st);
        int txo=trie[x][0];
        int too=1e9;
        if(tim[txo].lower_bound(st)!=tim[txo].end())too=*tim[txo].lower_bound(st);
        if(trie[x][0]!=0&&st<=too&&too<=fn)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][0],st,fn);
            return;
        }
        else if(trie[x][1]!=0&&st<=to1&&to1<=fn)
        {
            ans*=2;
            qu(s,z+1,trie[x][1],st,fn);
        }
    }
    else
    {
        int tx1=trie[x][1];
        int to1=1e9;
        if(tim[tx1].lower_bound(st)!=tim[tx1].end())to1=*tim[tx1].lower_bound(st);
        int txo=trie[x][0];
        int too=1e9;
        if(tim[txo].lower_bound(st)!=tim[txo].end())too=*tim[txo].lower_bound(st);
        if(trie[x][1]!=0&&st<=to1&&to1<=fn)
        {
            ans*=2;
            ans++;
            qu(s,z+1,trie[x][1],st,fn);
            return;
        }
        else if(trie[x][0]!=0&&st<=too&&too<=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;
    string ss=to(0);
    ad(ss,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,en[y],ot[y]);
            cout<<ans<<endl;
        }
    }
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 521852 KB Output is correct
2 Correct 330 ms 521976 KB Output is correct
3 Correct 329 ms 521976 KB Output is correct
4 Correct 333 ms 522144 KB Output is correct
5 Correct 329 ms 521848 KB Output is correct
6 Correct 337 ms 521848 KB Output is correct
7 Correct 332 ms 522040 KB Output is correct
8 Correct 335 ms 522104 KB Output is correct
9 Correct 333 ms 521848 KB Output is correct
10 Correct 323 ms 521848 KB Output is correct
11 Correct 332 ms 521976 KB Output is correct
12 Correct 335 ms 522104 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 521852 KB Output is correct
2 Correct 330 ms 521976 KB Output is correct
3 Correct 329 ms 521976 KB Output is correct
4 Correct 333 ms 522144 KB Output is correct
5 Correct 329 ms 521848 KB Output is correct
6 Correct 337 ms 521848 KB Output is correct
7 Correct 332 ms 522040 KB Output is correct
8 Correct 335 ms 522104 KB Output is correct
9 Correct 333 ms 521848 KB Output is correct
10 Correct 323 ms 521848 KB Output is correct
11 Correct 332 ms 521976 KB Output is correct
12 Correct 335 ms 522104 KB Output is correct
13 Correct 344 ms 522836 KB Output is correct
14 Correct 342 ms 523648 KB Output is correct
15 Runtime error 280 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 271 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 521852 KB Output is correct
2 Correct 330 ms 521976 KB Output is correct
3 Correct 329 ms 521976 KB Output is correct
4 Correct 333 ms 522144 KB Output is correct
5 Correct 329 ms 521848 KB Output is correct
6 Correct 337 ms 521848 KB Output is correct
7 Correct 332 ms 522040 KB Output is correct
8 Correct 335 ms 522104 KB Output is correct
9 Correct 333 ms 521848 KB Output is correct
10 Correct 323 ms 521848 KB Output is correct
11 Correct 332 ms 521976 KB Output is correct
12 Correct 335 ms 522104 KB Output is correct
13 Correct 344 ms 522836 KB Output is correct
14 Correct 342 ms 523648 KB Output is correct
15 Runtime error 280 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -