oj.uz

Submission #938770

# Submission time Handle Problem Language Result Execution time Memory
938770 2024-03-05T14:11:24 Z User0069 Klasika (COCI20_klasika) C++17
33 / 110
 525 ms 524288 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e6+1;
const int INF=1e9;
int n=1,q,a[maxn],b[maxn],in[maxn],out[maxn],cur,v[maxn];
string s[maxn];
vector<int> adj[maxn];
struct trie
{
    struct node
    {
        node* child[2];
        int cnt;
        node()
        {
            cnt=0;
            child[1]=child[0]=NULL;
        }
    };
    node* root;
    trie()
    {
        root=new node();
    }
    void add(int x)
    {
        node* cur=root;
        for(int i=30;i>=0;i--)
        {
            int c=(x>>i)&1;
            if(cur->child[c]==NULL) cur->child[c]=new node();
            cur=cur->child[c];
            cur->cnt++;
        }
    }
    int get(int x)
    {
        int ans=0;
        node* cur=root;
        for(int i=30;i>=0;i--)
        {
            int c=(x>>i)&1;
            if(cur->child[1^c]!=NULL)
            {
                ans+=(1<<i);
                cur=cur->child[1^c];
            }
            else if(cur->child[c]!=NULL) cur=cur->child[c];
            else return 0;
        }
        return ans;
    }
};
struct segtree
{
    trie ST[4*maxn];
    void update(int id,int cl,int cr,int pos,int val)
    {
        if(cl>pos||cr<pos) return;
        ST[id].add(val);
        if(cl==cr) return;
        int mid=(cl+cr)/2;
        if(pos<=mid) update(2*id,cl,mid,pos,val);
        else update(2*id+1,mid+1,cr,pos,val);
    }
    int get(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return 0;
        if(cl>=l&&cr<=r) return ST[id].get(val);
        int mid=(cl+cr)/2;
        return max(get(2*id,cl,mid,l,r,val),get(2*id+1,mid+1,cr,l,r,val));
    }
}f;
void dfs(int x,int par)
{
    in[x]=++cur;
    v[x]=v[par]^v[x];
    for(int y:adj[x])
    {
        dfs(y,x);
    }
    out[x]=cur;
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>s[i]>>a[i]>>b[i];
        if(s[i]=="Add")
        {
            adj[a[i]].push_back(++n);
            v[n]=b[i];
        }
    }
    dfs(1,0);
    int cc=1;
    f.update(1,1,n,1,0);
    for(int i=1;i<=q;i++)
    {
        if(s[i]=="Add")
        {
            ++cc;
            f.update(1,1,n,in[cc],v[cc]);
        }
        else
        {
            cout<<f.get(1,1,n,in[b[i]],out[b[i]],v[a[i]])<<"\n";
        }
    }
//    for(int i=1;i<=n;i++) cout<<v[i]<<" ";

}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 218508 KB Output is correct
2 Correct 119 ms 218492 KB Output is correct
3 Correct 117 ms 218928 KB Output is correct
4 Correct 120 ms 219068 KB Output is correct
5 Correct 116 ms 218260 KB Output is correct
6 Correct 117 ms 218452 KB Output is correct
7 Correct 117 ms 218924 KB Output is correct
8 Correct 123 ms 219472 KB Output is correct
9 Correct 116 ms 218452 KB Output is correct
10 Correct 118 ms 218708 KB Output is correct
11 Correct 116 ms 219048 KB Output is correct
12 Correct 123 ms 219456 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 218508 KB Output is correct
2 Correct 119 ms 218492 KB Output is correct
3 Correct 117 ms 218928 KB Output is correct
4 Correct 120 ms 219068 KB Output is correct
5 Correct 116 ms 218260 KB Output is correct
6 Correct 117 ms 218452 KB Output is correct
7 Correct 117 ms 218924 KB Output is correct
8 Correct 123 ms 219472 KB Output is correct
9 Correct 116 ms 218452 KB Output is correct
10 Correct 118 ms 218708 KB Output is correct
11 Correct 116 ms 219048 KB Output is correct
12 Correct 123 ms 219456 KB Output is correct
13 Correct 119 ms 221620 KB Output is correct
14 Correct 127 ms 225576 KB Output is correct
15 Correct 127 ms 229700 KB Output is correct
16 Correct 143 ms 233660 KB Output is correct
17 Correct 121 ms 221268 KB Output is correct
18 Correct 123 ms 225108 KB Output is correct
19 Correct 125 ms 229492 KB Output is correct
20 Correct 133 ms 233180 KB Output is correct
21 Correct 119 ms 221344 KB Output is correct
22 Correct 125 ms 225360 KB Output is correct
23 Correct 128 ms 229280 KB Output is correct
24 Correct 133 ms 233392 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 525 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 218508 KB Output is correct
2 Correct 119 ms 218492 KB Output is correct
3 Correct 117 ms 218928 KB Output is correct
4 Correct 120 ms 219068 KB Output is correct
5 Correct 116 ms 218260 KB Output is correct
6 Correct 117 ms 218452 KB Output is correct
7 Correct 117 ms 218924 KB Output is correct
8 Correct 123 ms 219472 KB Output is correct
9 Correct 116 ms 218452 KB Output is correct
10 Correct 118 ms 218708 KB Output is correct
11 Correct 116 ms 219048 KB Output is correct
12 Correct 123 ms 219456 KB Output is correct
13 Correct 119 ms 221620 KB Output is correct
14 Correct 127 ms 225576 KB Output is correct
15 Correct 127 ms 229700 KB Output is correct
16 Correct 143 ms 233660 KB Output is correct
17 Correct 121 ms 221268 KB Output is correct
18 Correct 123 ms 225108 KB Output is correct
19 Correct 125 ms 229492 KB Output is correct
20 Correct 133 ms 233180 KB Output is correct
21 Correct 119 ms 221344 KB Output is correct
22 Correct 125 ms 225360 KB Output is correct
23 Correct 128 ms 229280 KB Output is correct
24 Correct 133 ms 233392 KB Output is correct
25 Runtime error 525 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -