oj.uz

Submission #1094101

# Submission time Handle Problem Language Result Execution time Memory
1094101 2024-09-28T12:19:15 Z 0pt1mus23 Klasika (COCI20_klasika) C++14
33 / 110
 1135 ms 389592 KB 
#include <bits/stdc++.h>
using namespace std;
#define needforspeed ios::sync_with_stdio(0);cin.tie(0);
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9 +7,sze = 5e5 +23,inf = INT_MAX, L = 31; 
unordered_map<int,int> T[sze];
set<int> fener[sze];
int tnod = 1;
int discover[sze];
int finish[sze];
vector<pair<int,int>> graph[sze];
 
void add(int node,int bit,int val,int gir){
    if(bit<0){
        return;
    }
    int x =0;
    if(val & (1<<bit)){
        x=1;
    }
    if(T[node][x]==0){
       T[node][x]= ( ++tnod);
    }
    // cout<<bit<<" added "<<val<<" "<<x<<endl;
    fener[T[node][x]].ins(gir);
    add(T[node][x],bit-1,val,gir);
}
int timer =0;
int pref[sze];
void dfs(int node,int par,int px){
    discover[node]=++timer;
    pref[node]=px;
    for(auto v:graph[node]){
        if(v.first!=par){
            dfs(v.first,node,px ^ v.second);
        }
    }
    finish[node]=++timer;   
}
 
int qry(int node,int bit,int val,int l,int r){
    if(bit<0){
        return 0;
    }
    int lazim =1;
    if(val & (1<<bit)){
        lazim=0;
    }
    // cout<<bit<<" "<<val<<" "<<lazim<<" "<<T[node][lazim]<<endl;
    if(T[node][lazim] && fener[T[node][lazim]].lower_bound(l) != fener[T[node][lazim]].upper_bound(r)){
        return (1<<bit) + qry(T[node][lazim],bit-1,val,l,r);
    }
    else{
        return qry(T[node][1 - lazim],bit-1,val,l,r);
    }
}
void opt1z(){
    int q;
    cin>>q;
    int nodec =2;
    vector<pair<int, pair<int,int>>> queries;
    for(int i=0;i<q;i++){
        string op;cin>>op;
        int a,b;
        cin>>a>>b;
        if(op=="Add"){
            graph[a].pb({nodec,b});
            graph[nodec].pb({a,b});
            queries.pb({0,{nodec,b}});
            nodec++;
        }
        else{
            queries.pb({1,{a,b}});
        }
    }
    dfs(1,-1,0);
    add(1,L,0,discover[1]);
    // cout<<pref[2]<<endl;
    for(auto v:queries){
        auto [a,b] = v.second;
        if(v.first ==0){
            add(1,L,pref[a],discover[a]);
        }
        else{
            // cout<<"sa"<<endl;
            cout<<qry(1,L,pref[a],discover[b],finish[b])<<endl;
        }
    }
}
 
signed main() {
    needforspeed;
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Compilation message

klasika.cpp: In function 'void opt1z()':
klasika.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         auto [a,b] = v.second;
      |              ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63324 KB Output is correct
2 Correct 27 ms 63404 KB Output is correct
3 Correct 28 ms 63580 KB Output is correct
4 Correct 28 ms 63824 KB Output is correct
5 Correct 27 ms 63320 KB Output is correct
6 Correct 28 ms 63312 KB Output is correct
7 Correct 27 ms 63580 KB Output is correct
8 Correct 28 ms 63888 KB Output is correct
9 Correct 28 ms 63316 KB Output is correct
10 Correct 28 ms 63580 KB Output is correct
11 Correct 28 ms 63680 KB Output is correct
12 Correct 38 ms 63764 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63324 KB Output is correct
2 Correct 27 ms 63404 KB Output is correct
3 Correct 28 ms 63580 KB Output is correct
4 Correct 28 ms 63824 KB Output is correct
5 Correct 27 ms 63320 KB Output is correct
6 Correct 28 ms 63312 KB Output is correct
7 Correct 27 ms 63580 KB Output is correct
8 Correct 28 ms 63888 KB Output is correct
9 Correct 28 ms 63316 KB Output is correct
10 Correct 28 ms 63580 KB Output is correct
11 Correct 28 ms 63680 KB Output is correct
12 Correct 38 ms 63764 KB Output is correct
13 Correct 37 ms 65116 KB Output is correct
14 Correct 41 ms 66892 KB Output is correct
15 Correct 42 ms 68780 KB Output is correct
16 Correct 48 ms 70224 KB Output is correct
17 Correct 37 ms 65104 KB Output is correct
18 Correct 41 ms 66796 KB Output is correct
19 Correct 43 ms 68700 KB Output is correct
20 Correct 46 ms 70120 KB Output is correct
21 Correct 38 ms 65112 KB Output is correct
22 Correct 39 ms 66760 KB Output is correct
23 Correct 43 ms 68444 KB Output is correct
24 Correct 48 ms 69976 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1135 ms 389592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63324 KB Output is correct
2 Correct 27 ms 63404 KB Output is correct
3 Correct 28 ms 63580 KB Output is correct
4 Correct 28 ms 63824 KB Output is correct
5 Correct 27 ms 63320 KB Output is correct
6 Correct 28 ms 63312 KB Output is correct
7 Correct 27 ms 63580 KB Output is correct
8 Correct 28 ms 63888 KB Output is correct
9 Correct 28 ms 63316 KB Output is correct
10 Correct 28 ms 63580 KB Output is correct
11 Correct 28 ms 63680 KB Output is correct
12 Correct 38 ms 63764 KB Output is correct
13 Correct 37 ms 65116 KB Output is correct
14 Correct 41 ms 66892 KB Output is correct
15 Correct 42 ms 68780 KB Output is correct
16 Correct 48 ms 70224 KB Output is correct
17 Correct 37 ms 65104 KB Output is correct
18 Correct 41 ms 66796 KB Output is correct
19 Correct 43 ms 68700 KB Output is correct
20 Correct 46 ms 70120 KB Output is correct
21 Correct 38 ms 65112 KB Output is correct
22 Correct 39 ms 66760 KB Output is correct
23 Correct 43 ms 68444 KB Output is correct
24 Correct 48 ms 69976 KB Output is correct
25 Runtime error 1135 ms 389592 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -