oj.uz

Submission #893142

# Submission time Handle Problem Language Result Execution time Memory
893142 2023-12-26T14:55:38 Z Alora Klasika (COCI20_klasika) C++17
33 / 110
 163 ms 82760 KB 
#include <bits/stdc++.h>
#define Alora "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define all(v) v.begin(), v.end()
#define pb push_back
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int Q, n, m, a[maxn];
vector <int> g[maxn];
struct dl{int x, y, time;}b[maxn];

int in[maxn*30], out[maxn*30], tmp;
void dfs(int u){
    in[u] = ++tmp;
    for(auto v: g[u]) dfs(v);
    out[u] = tmp;
}

int xd[maxn*30][3], mi[maxn*30], ma[maxn*30], cnt;
void add(int num, int time){
    int tt = 0;
    fid(i, 30, 0){
        int c = getbit(num, i);
        if(xd[tt][c] == 0) xd[tt][c] = ++cnt;
        tt = xd[tt][c];
        mi[tt] = min(mi[tt], time);
        ma[tt] = max(ma[tt], time);
    }
}

bool check(int tt, int l, int r){
    if(tt == 0) return 0;
    return (mi[tt] <= r && ma[tt] >= l);
}
int get(int l, int r, int num){
    int tt = 0, ans = 0;
    fid(i, 30, 0){
        int c = getbit(num, i);
        if(check(xd[tt][1 - c], l, r)){
          //  cout << i << " " << xd[tt][1 - c] << " " << (1 << i) << endl;
            ans += (1 << i);
            tt = xd[tt][1 - c];
        }
        else tt = xd[tt][c];
    }
    return ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	if(fopen(Alora".inp", "r")){
    freopen(Alora".inp", "r", stdin);
    freopen(Alora".out", "w", stdout);}
    cin >> Q;
    n = 1;
    fi(i, 1, Q){
        string s; int x, y;
        cin >> s >> x >> y;
        if(s == "Add"){
            a[++n] = a[x] ^ y;
            g[x].pb(n);
            b[i] = {0, n, n};
        }
        else b[i] = {1, x, y};
    }
    dfs(1);
    memset(mi, 60, sizeof(mi));
    add(0, 1);
    fi(i, 1, Q){
        auto[t, x, y] = b[i];
        if(t == 0) add(a[x], in[x]);
        else{
            cout << get(in[y], out[y], a[x]) << '\n';
        }
    }
    return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:59:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34140 KB Output is correct
2 Correct 5 ms 34264 KB Output is correct
3 Correct 5 ms 34140 KB Output is correct
4 Correct 5 ms 34244 KB Output is correct
5 Incorrect 5 ms 34140 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34140 KB Output is correct
2 Correct 5 ms 34264 KB Output is correct
3 Correct 5 ms 34140 KB Output is correct
4 Correct 5 ms 34244 KB Output is correct
5 Incorrect 5 ms 34140 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 50868 KB Output is correct
2 Correct 133 ms 61948 KB Output is correct
3 Correct 138 ms 72532 KB Output is correct
4 Correct 143 ms 82760 KB Output is correct
5 Correct 122 ms 49488 KB Output is correct
6 Correct 122 ms 58584 KB Output is correct
7 Correct 135 ms 67664 KB Output is correct
8 Correct 156 ms 76372 KB Output is correct
9 Correct 102 ms 49340 KB Output is correct
10 Correct 120 ms 59260 KB Output is correct
11 Correct 129 ms 68664 KB Output is correct
12 Correct 163 ms 77824 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34140 KB Output is correct
2 Correct 5 ms 34264 KB Output is correct
3 Correct 5 ms 34140 KB Output is correct
4 Correct 5 ms 34244 KB Output is correct
5 Incorrect 5 ms 34140 KB Output isn't correct
6 Halted 0 ms 0 KB -