oj.uz

Submission #199877

# Submission time Handle Problem Language Result Execution time Memory
199877 2020-02-03T22:31:33 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 3044 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,a[200005],k,trie[5000006][4],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 295 ms 427896 KB Output is correct
2 Correct 277 ms 428152 KB Output is correct
3 Correct 281 ms 428024 KB Output is correct
4 Correct 273 ms 428284 KB Output is correct
5 Correct 281 ms 427896 KB Output is correct
6 Correct 287 ms 427896 KB Output is correct
7 Correct 277 ms 428024 KB Output is correct
8 Correct 283 ms 428152 KB Output is correct
9 Correct 283 ms 427896 KB Output is correct
10 Correct 279 ms 428024 KB Output is correct
11 Correct 274 ms 428024 KB Output is correct
12 Correct 296 ms 428152 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 427896 KB Output is correct
2 Correct 277 ms 428152 KB Output is correct
3 Correct 281 ms 428024 KB Output is correct
4 Correct 273 ms 428284 KB Output is correct
5 Correct 281 ms 427896 KB Output is correct
6 Correct 287 ms 427896 KB Output is correct
7 Correct 277 ms 428024 KB Output is correct
8 Correct 283 ms 428152 KB Output is correct
9 Correct 283 ms 427896 KB Output is correct
10 Correct 279 ms 428024 KB Output is correct
11 Correct 274 ms 428024 KB Output is correct
12 Correct 296 ms 428152 KB Output is correct
13 Correct 290 ms 428896 KB Output is correct
14 Correct 298 ms 429816 KB Output is correct
15 Correct 302 ms 430584 KB Output is correct
16 Correct 309 ms 431736 KB Output is correct
17 Correct 292 ms 428792 KB Output is correct
18 Correct 310 ms 429688 KB Output is correct
19 Correct 309 ms 430584 KB Output is correct
20 Correct 291 ms 431480 KB Output is correct
21 Correct 298 ms 428792 KB Output is correct
22 Correct 292 ms 429668 KB Output is correct
23 Correct 284 ms 430588 KB Output is correct
24 Correct 315 ms 431352 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3044 ms 521000 KB Output is correct
2 Runtime error 1626 ms 524288 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 295 ms 427896 KB Output is correct
2 Correct 277 ms 428152 KB Output is correct
3 Correct 281 ms 428024 KB Output is correct
4 Correct 273 ms 428284 KB Output is correct
5 Correct 281 ms 427896 KB Output is correct
6 Correct 287 ms 427896 KB Output is correct
7 Correct 277 ms 428024 KB Output is correct
8 Correct 283 ms 428152 KB Output is correct
9 Correct 283 ms 427896 KB Output is correct
10 Correct 279 ms 428024 KB Output is correct
11 Correct 274 ms 428024 KB Output is correct
12 Correct 296 ms 428152 KB Output is correct
13 Correct 290 ms 428896 KB Output is correct
14 Correct 298 ms 429816 KB Output is correct
15 Correct 302 ms 430584 KB Output is correct
16 Correct 309 ms 431736 KB Output is correct
17 Correct 292 ms 428792 KB Output is correct
18 Correct 310 ms 429688 KB Output is correct
19 Correct 309 ms 430584 KB Output is correct
20 Correct 291 ms 431480 KB Output is correct
21 Correct 298 ms 428792 KB Output is correct
22 Correct 292 ms 429668 KB Output is correct
23 Correct 284 ms 430588 KB Output is correct
24 Correct 315 ms 431352 KB Output is correct
25 Correct 3044 ms 521000 KB Output is correct
26 Runtime error 1626 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -