oj.uz

Submission #199878

# Submission time Handle Problem Language Result Execution time Memory
199878 2020-02-03T22:32:15 Z mdn2002 Klasika (COCI20_klasika) C++14
33 / 110
 1206 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[10000006];
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 292 ms 474872 KB Output is correct
2 Correct 303 ms 474872 KB Output is correct
3 Correct 308 ms 475064 KB Output is correct
4 Correct 300 ms 475128 KB Output is correct
5 Correct 305 ms 474872 KB Output is correct
6 Correct 294 ms 474872 KB Output is correct
7 Correct 309 ms 475048 KB Output is correct
8 Correct 301 ms 475256 KB Output is correct
9 Correct 302 ms 474872 KB Output is correct
10 Correct 300 ms 474964 KB Output is correct
11 Correct 307 ms 475000 KB Output is correct
12 Correct 309 ms 475128 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 474872 KB Output is correct
2 Correct 303 ms 474872 KB Output is correct
3 Correct 308 ms 475064 KB Output is correct
4 Correct 300 ms 475128 KB Output is correct
5 Correct 305 ms 474872 KB Output is correct
6 Correct 294 ms 474872 KB Output is correct
7 Correct 309 ms 475048 KB Output is correct
8 Correct 301 ms 475256 KB Output is correct
9 Correct 302 ms 474872 KB Output is correct
10 Correct 300 ms 474964 KB Output is correct
11 Correct 307 ms 475000 KB Output is correct
12 Correct 309 ms 475128 KB Output is correct
13 Correct 316 ms 475768 KB Output is correct
14 Correct 307 ms 476792 KB Output is correct
15 Correct 311 ms 477560 KB Output is correct
16 Correct 310 ms 478456 KB Output is correct
17 Correct 311 ms 475768 KB Output is correct
18 Correct 313 ms 476664 KB Output is correct
19 Correct 311 ms 477560 KB Output is correct
20 Correct 317 ms 478332 KB Output is correct
21 Correct 306 ms 475768 KB Output is correct
22 Correct 308 ms 476664 KB Output is correct
23 Correct 305 ms 477432 KB Output is correct
24 Correct 319 ms 478328 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1206 ms 524292 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 292 ms 474872 KB Output is correct
2 Correct 303 ms 474872 KB Output is correct
3 Correct 308 ms 475064 KB Output is correct
4 Correct 300 ms 475128 KB Output is correct
5 Correct 305 ms 474872 KB Output is correct
6 Correct 294 ms 474872 KB Output is correct
7 Correct 309 ms 475048 KB Output is correct
8 Correct 301 ms 475256 KB Output is correct
9 Correct 302 ms 474872 KB Output is correct
10 Correct 300 ms 474964 KB Output is correct
11 Correct 307 ms 475000 KB Output is correct
12 Correct 309 ms 475128 KB Output is correct
13 Correct 316 ms 475768 KB Output is correct
14 Correct 307 ms 476792 KB Output is correct
15 Correct 311 ms 477560 KB Output is correct
16 Correct 310 ms 478456 KB Output is correct
17 Correct 311 ms 475768 KB Output is correct
18 Correct 313 ms 476664 KB Output is correct
19 Correct 311 ms 477560 KB Output is correct
20 Correct 317 ms 478332 KB Output is correct
21 Correct 306 ms 475768 KB Output is correct
22 Correct 308 ms 476664 KB Output is correct
23 Correct 305 ms 477432 KB Output is correct
24 Correct 319 ms 478328 KB Output is correct
25 Runtime error 1206 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -