oj.uz

Submission #965541

# Submission time Handle Problem Language Result Execution time Memory
965541 2024-04-18T20:17:25 Z dosts Klasika (COCI20_klasika) C++17
33 / 110
 670 ms 524288 KB 
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+100,inf = 1e18,MOD = 1e9+7,B = 30;


struct Trie {
    Trie* children[2] = {NULL,NULL};
    int bas = 0;
    void insert(int x) {
        Trie* cur = this;
        for (int i=30;i>=-1;i--) {
            cur->bas++;
            if (i > -1) {
                bool go = x&(1<<i);
                if (!cur->children[go]) cur->children[go] = new Trie;
                cur = cur->children[go];
            }
        }
    }

    int query(int x) {
        if (!bas) return -inf;
        Trie* cur = this;
        int ans = 0;
        for (int i=30;i>=0;i--) {
            bool go = !(x&(1<<i));
            if (cur->children[go] && cur->children[go]->bas) {
                ans+=(1<<i);
                cur = cur->children[go];
            } else {
                if (!cur->children[!go]) cur->children[!go] = new Trie;
                cur = cur->children[!go];
            }
        }
        return ans;
    }

};


struct ST {
    vector<Trie*> t;

    ST(int nn) {
        t.resize(4*nn+1);
        for (int i=1;i<=4*nn;i++) t[i] = new Trie;
    }

    void update(int node,int l,int r,int p,int put) {
        t[node]->insert(put);
        if (l==r) return;
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,put);
        else update(2*node+1,m+1,r,p,put);
    }
    int query(int node,int l,int r,int L,int R,int v) {
        if (l > R || r < L) return -inf;
        if (l >= L && r <= R) return t[node]->query(v);
        int m = (l+r) >> 1;
        return max(query(2*node,l,m,L,R,v),query(2*node+1,m+1,r,L,R,v)); 
    }
};

vi tin(N),tout(N),d(N),edges[N];
int timer = 1;
void dfs(int node) {
    tin[node] = timer++;
    for (auto it : edges[node]) dfs(it);
    tout[node] = timer-1;
}

void solve() {
    d[1] = 0;
    int curnode = 1;
    int q;
    cin >> q;
    vector<pair<int,pii>> qs(q+1);
    for (int i=1;i<=q;i++) {
        string s;
        cin >> s;
        int node,v;
        cin >> node >> v;
        if (s == "Add") {
            edges[node].push_back(++curnode);
            d[curnode] = d[node]^v; 
        }
        qs[i] = (pair<int,pii>{(s != "Add"), pii{node,v}});
    }
    dfs(1);
    ST st(curnode);
    st.update(1,1,curnode,tin[1],0);
    int curry = 1;
    for (int i=1;i<=q;i++) {
        int type = qs[i].ff;
        if (!type) {
            ++curry;
            st.update(1,1,curnode,tin[curry],d[curry]);
        }
        else {
            auto [a,b] = qs[i].ss;
            cout << st.query(1,1,curnode,tin[b],tout[b],d[a]) << '\n';
        }
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message

klasika.cpp:11:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int N = 2e5+100,inf = 1e18,MOD = 1e9+7,B = 30;
      |                             ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 7768 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 3 ms 8372 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 7768 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 3 ms 8372 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 8 ms 11100 KB Output is correct
14 Correct 12 ms 14940 KB Output is correct
15 Correct 15 ms 19048 KB Output is correct
16 Correct 19 ms 23132 KB Output is correct
17 Correct 7 ms 10844 KB Output is correct
18 Correct 13 ms 14584 KB Output is correct
19 Correct 15 ms 18984 KB Output is correct
20 Correct 19 ms 22876 KB Output is correct
21 Correct 8 ms 10844 KB Output is correct
22 Correct 11 ms 14744 KB Output is correct
23 Correct 15 ms 18780 KB Output is correct
24 Correct 22 ms 22732 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 500012 KB Output is correct
2 Runtime error 620 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 7768 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 3 ms 8372 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 8 ms 11100 KB Output is correct
14 Correct 12 ms 14940 KB Output is correct
15 Correct 15 ms 19048 KB Output is correct
16 Correct 19 ms 23132 KB Output is correct
17 Correct 7 ms 10844 KB Output is correct
18 Correct 13 ms 14584 KB Output is correct
19 Correct 15 ms 18984 KB Output is correct
20 Correct 19 ms 22876 KB Output is correct
21 Correct 8 ms 10844 KB Output is correct
22 Correct 11 ms 14744 KB Output is correct
23 Correct 15 ms 18780 KB Output is correct
24 Correct 22 ms 22732 KB Output is correct
25 Correct 670 ms 500012 KB Output is correct
26 Runtime error 620 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -