oj.uz

Submission #1094091

# Submission time Handle Problem Language Result Execution time Memory
1094091 2024-09-28T12:11:51 Z 0pt1mus23 Klasika (COCI20_klasika) C++14
33 / 110
 94 ms 65276 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 = 1e5 +23,inf = INT_MAX, L = 30; 
int T[sze][2];
set<int> fener[sze][2];
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[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[node][lazim].lower_bound(l) != fener[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 6 ms 12120 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 6 ms 12376 KB Output is correct
4 Correct 5 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 6 ms 12220 KB Output is correct
8 Correct 5 ms 12380 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12476 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 6 ms 12376 KB Output is correct
4 Correct 5 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 6 ms 12220 KB Output is correct
8 Correct 5 ms 12380 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12476 KB Output is correct
13 Correct 7 ms 12892 KB Output is correct
14 Correct 8 ms 13708 KB Output is correct
15 Correct 10 ms 14428 KB Output is correct
16 Correct 10 ms 15176 KB Output is correct
17 Correct 8 ms 13004 KB Output is correct
18 Correct 9 ms 13916 KB Output is correct
19 Correct 9 ms 14428 KB Output is correct
20 Correct 10 ms 15076 KB Output is correct
21 Correct 7 ms 12904 KB Output is correct
22 Correct 9 ms 13720 KB Output is correct
23 Correct 10 ms 14424 KB Output is correct
24 Correct 11 ms 15196 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 65276 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 6 ms 12120 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 6 ms 12376 KB Output is correct
4 Correct 5 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 6 ms 12220 KB Output is correct
8 Correct 5 ms 12380 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12476 KB Output is correct
13 Correct 7 ms 12892 KB Output is correct
14 Correct 8 ms 13708 KB Output is correct
15 Correct 10 ms 14428 KB Output is correct
16 Correct 10 ms 15176 KB Output is correct
17 Correct 8 ms 13004 KB Output is correct
18 Correct 9 ms 13916 KB Output is correct
19 Correct 9 ms 14428 KB Output is correct
20 Correct 10 ms 15076 KB Output is correct
21 Correct 7 ms 12904 KB Output is correct
22 Correct 9 ms 13720 KB Output is correct
23 Correct 10 ms 14424 KB Output is correct
24 Correct 11 ms 15196 KB Output is correct
25 Runtime error 94 ms 65276 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -