oj.uz

Submission #199894

# Submission time Handle Problem Language Result Execution time Memory
199894 2020-02-03T22:53:21 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 2796 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[200005],k,trie[2000006][3],ans;
int en[200005],ot[200005],tmm;
vector<int>gr[200005],aq,bq;
vector<string>sq;
set<int>tim[9000006];
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 273 ms 427900 KB Output is correct
2 Correct 268 ms 427896 KB Output is correct
3 Correct 275 ms 428024 KB Output is correct
4 Correct 275 ms 428024 KB Output is correct
5 Correct 276 ms 427768 KB Output is correct
6 Correct 275 ms 428024 KB Output is correct
7 Correct 271 ms 427896 KB Output is correct
8 Correct 271 ms 428152 KB Output is correct
9 Correct 274 ms 427896 KB Output is correct
10 Correct 270 ms 427896 KB Output is correct
11 Correct 276 ms 428152 KB Output is correct
12 Correct 276 ms 428024 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 427900 KB Output is correct
2 Correct 268 ms 427896 KB Output is correct
3 Correct 275 ms 428024 KB Output is correct
4 Correct 275 ms 428024 KB Output is correct
5 Correct 276 ms 427768 KB Output is correct
6 Correct 275 ms 428024 KB Output is correct
7 Correct 271 ms 427896 KB Output is correct
8 Correct 271 ms 428152 KB Output is correct
9 Correct 274 ms 427896 KB Output is correct
10 Correct 270 ms 427896 KB Output is correct
11 Correct 276 ms 428152 KB Output is correct
12 Correct 276 ms 428024 KB Output is correct
13 Correct 285 ms 428664 KB Output is correct
14 Correct 277 ms 429304 KB Output is correct
15 Correct 286 ms 430072 KB Output is correct
16 Correct 280 ms 430840 KB Output is correct
17 Correct 287 ms 428536 KB Output is correct
18 Correct 278 ms 429304 KB Output is correct
19 Correct 291 ms 430072 KB Output is correct
20 Correct 292 ms 430712 KB Output is correct
21 Correct 322 ms 428668 KB Output is correct
22 Correct 286 ms 429304 KB Output is correct
23 Correct 283 ms 429944 KB Output is correct
24 Correct 287 ms 430712 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2796 ms 508184 KB Output is correct
2 Runtime error 1832 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 427900 KB Output is correct
2 Correct 268 ms 427896 KB Output is correct
3 Correct 275 ms 428024 KB Output is correct
4 Correct 275 ms 428024 KB Output is correct
5 Correct 276 ms 427768 KB Output is correct
6 Correct 275 ms 428024 KB Output is correct
7 Correct 271 ms 427896 KB Output is correct
8 Correct 271 ms 428152 KB Output is correct
9 Correct 274 ms 427896 KB Output is correct
10 Correct 270 ms 427896 KB Output is correct
11 Correct 276 ms 428152 KB Output is correct
12 Correct 276 ms 428024 KB Output is correct
13 Correct 285 ms 428664 KB Output is correct
14 Correct 277 ms 429304 KB Output is correct
15 Correct 286 ms 430072 KB Output is correct
16 Correct 280 ms 430840 KB Output is correct
17 Correct 287 ms 428536 KB Output is correct
18 Correct 278 ms 429304 KB Output is correct
19 Correct 291 ms 430072 KB Output is correct
20 Correct 292 ms 430712 KB Output is correct
21 Correct 322 ms 428668 KB Output is correct
22 Correct 286 ms 429304 KB Output is correct
23 Correct 283 ms 429944 KB Output is correct
24 Correct 287 ms 430712 KB Output is correct
25 Correct 2796 ms 508184 KB Output is correct
26 Runtime error 1832 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -