oj.uz

Submission #893155

# Submission time Handle Problem Language Result Execution time Memory
893155 2023-12-26T15:10:36 Z Alora Klasika (COCI20_klasika) C++17
33 / 110
 3581 ms 524288 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], out[maxn], tmp;
void dfs(int u){
    in[u] = ++tmp;
    for(auto v: g[u]) dfs(v);
    out[u] = tmp;
}

int xd[maxn*10][3], cnt;
set <int> st[maxn*10];

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];
        st[tt].insert(time);
    }
}

bool check(int tt, int l, int r){
    if(tt == 0) return 0;
    auto it = st[tt].lower_bound(l);
    if(it == st[tt].end()) return 0;
    return (*it <= r) ;
}
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)){
            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);
    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:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 101720 KB Output is correct
2 Correct 21 ms 101976 KB Output is correct
3 Correct 20 ms 101980 KB Output is correct
4 Correct 20 ms 101980 KB Output is correct
5 Correct 20 ms 101724 KB Output is correct
6 Correct 20 ms 101980 KB Output is correct
7 Correct 20 ms 101980 KB Output is correct
8 Correct 20 ms 101980 KB Output is correct
9 Correct 20 ms 101720 KB Output is correct
10 Correct 20 ms 102232 KB Output is correct
11 Correct 20 ms 101952 KB Output is correct
12 Correct 21 ms 101972 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 101720 KB Output is correct
2 Correct 21 ms 101976 KB Output is correct
3 Correct 20 ms 101980 KB Output is correct
4 Correct 20 ms 101980 KB Output is correct
5 Correct 20 ms 101724 KB Output is correct
6 Correct 20 ms 101980 KB Output is correct
7 Correct 20 ms 101980 KB Output is correct
8 Correct 20 ms 101980 KB Output is correct
9 Correct 20 ms 101720 KB Output is correct
10 Correct 20 ms 102232 KB Output is correct
11 Correct 20 ms 101952 KB Output is correct
12 Correct 21 ms 101972 KB Output is correct
13 Correct 22 ms 102492 KB Output is correct
14 Correct 23 ms 103004 KB Output is correct
15 Correct 24 ms 103516 KB Output is correct
16 Correct 25 ms 104284 KB Output is correct
17 Correct 23 ms 102236 KB Output is correct
18 Correct 23 ms 103000 KB Output is correct
19 Correct 24 ms 103516 KB Output is correct
20 Correct 25 ms 104028 KB Output is correct
21 Correct 22 ms 102236 KB Output is correct
22 Correct 23 ms 102944 KB Output is correct
23 Correct 24 ms 103512 KB Output is correct
24 Correct 24 ms 104016 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 172756 KB Output is correct
2 Correct 914 ms 239804 KB Output is correct
3 Correct 1300 ms 305440 KB Output is correct
4 Runtime error 3581 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 101720 KB Output is correct
2 Correct 21 ms 101976 KB Output is correct
3 Correct 20 ms 101980 KB Output is correct
4 Correct 20 ms 101980 KB Output is correct
5 Correct 20 ms 101724 KB Output is correct
6 Correct 20 ms 101980 KB Output is correct
7 Correct 20 ms 101980 KB Output is correct
8 Correct 20 ms 101980 KB Output is correct
9 Correct 20 ms 101720 KB Output is correct
10 Correct 20 ms 102232 KB Output is correct
11 Correct 20 ms 101952 KB Output is correct
12 Correct 21 ms 101972 KB Output is correct
13 Correct 22 ms 102492 KB Output is correct
14 Correct 23 ms 103004 KB Output is correct
15 Correct 24 ms 103516 KB Output is correct
16 Correct 25 ms 104284 KB Output is correct
17 Correct 23 ms 102236 KB Output is correct
18 Correct 23 ms 103000 KB Output is correct
19 Correct 24 ms 103516 KB Output is correct
20 Correct 25 ms 104028 KB Output is correct
21 Correct 22 ms 102236 KB Output is correct
22 Correct 23 ms 102944 KB Output is correct
23 Correct 24 ms 103512 KB Output is correct
24 Correct 24 ms 104016 KB Output is correct
25 Correct 483 ms 172756 KB Output is correct
26 Correct 914 ms 239804 KB Output is correct
27 Correct 1300 ms 305440 KB Output is correct
28 Runtime error 3581 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -