oj.uz

Submission #940779

# Submission time Handle Problem Language Result Execution time Memory
940779 2024-03-07T15:46:14 Z User0069 Klasika (COCI20_klasika) C++17
33 / 110
 1898 ms 433744 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=2e5+6;
const int INF=1e9;
vector<int> adj[maxn];
int q,n,in[maxn],out[maxn],a[maxn],b[maxn],v[maxn],cur;
string s[maxn];
struct node
{
    node* child[2];
    set<int> s;
    node()
    {
        child[1]=child[0]=NULL;
    }
};
node* root=new node();
bool f(node* kk,int l,int r)
{
    if(kk==NULL) return 0;
    if(*(kk->s.begin())>r||*(kk->s.rbegin())<l) return 0;
    return 1;
}
void add(int x,int val)
{
    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->s.insert(val);
    }
}
int get(int val,int l,int r)
{
    node* cur =root;
    int ans=0;
    for(int i=30;i>=0;i--)
    {
        int c=(val>>i)&1;
        if(f(cur->child[1^c],l,r))
        {
            ans+=(1<<i);
            cur=cur->child[1^c];
        }
        else cur=cur->child[c];
    }
    return ans;
}
void dfs(int x)
{
    in[x]=++cur;
    for(int y:adj[x])
    {
        dfs(y);
    }
    out[x]=cur;
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>q;
    n=1;
    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]^v[a[i]];
        }
    }
    dfs(1);
    cur=1;
    add(v[1],in[1]);
    for(int i=1;i<=q;i++)
    {
        if(s[i]=="Add")
        {
            ++cur;
            add(v[cur],in[cur]);
        }
        else
        {
            cout<<get(v[a[i]],in[b[i]],out[b[i]])<<"\n";
        }
    }
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15448 KB Output is correct
2 Correct 3 ms 15584 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 5 ms 15804 KB Output is correct
5 Runtime error 15 ms 30692 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15448 KB Output is correct
2 Correct 3 ms 15584 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 5 ms 15804 KB Output is correct
5 Runtime error 15 ms 30692 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 129228 KB Output is correct
2 Correct 772 ms 233564 KB Output is correct
3 Correct 1239 ms 333544 KB Output is correct
4 Correct 1897 ms 433744 KB Output is correct
5 Correct 487 ms 127932 KB Output is correct
6 Correct 877 ms 230712 KB Output is correct
7 Correct 1392 ms 329440 KB Output is correct
8 Correct 1898 ms 428132 KB Output is correct
9 Correct 448 ms 127720 KB Output is correct
10 Correct 772 ms 231512 KB Output is correct
11 Correct 1258 ms 331404 KB Output is correct
12 Correct 1628 ms 429908 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15448 KB Output is correct
2 Correct 3 ms 15584 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 5 ms 15804 KB Output is correct
5 Runtime error 15 ms 30692 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -