oj.uz

Submission #965540

# Submission time Handle Problem Language Result Execution time Memory
965540 2024-04-18T20:15:58 Z dosts Klasika (COCI20_klasika) C++17
33 / 110
 690 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();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 4 ms 10332 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 10332 KB Output is correct
7 Correct 4 ms 10588 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 6 ms 10436 KB Output is correct
11 Correct 4 ms 10584 KB Output is correct
12 Correct 5 ms 10840 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 4 ms 10332 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 10332 KB Output is correct
7 Correct 4 ms 10588 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 6 ms 10436 KB Output is correct
11 Correct 4 ms 10584 KB Output is correct
12 Correct 5 ms 10840 KB Output is correct
13 Correct 9 ms 13404 KB Output is correct
14 Correct 13 ms 17244 KB Output is correct
15 Correct 18 ms 21424 KB Output is correct
16 Correct 20 ms 25436 KB Output is correct
17 Correct 8 ms 13144 KB Output is correct
18 Correct 13 ms 17192 KB Output is correct
19 Correct 16 ms 21340 KB Output is correct
20 Correct 20 ms 25180 KB Output is correct
21 Correct 8 ms 13148 KB Output is correct
22 Correct 14 ms 17212 KB Output is correct
23 Correct 17 ms 21232 KB Output is correct
24 Correct 21 ms 25176 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 504656 KB Output is correct
2 Runtime error 690 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 10076 KB Output is correct
2 Correct 4 ms 10332 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 10332 KB Output is correct
7 Correct 4 ms 10588 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 6 ms 10436 KB Output is correct
11 Correct 4 ms 10584 KB Output is correct
12 Correct 5 ms 10840 KB Output is correct
13 Correct 9 ms 13404 KB Output is correct
14 Correct 13 ms 17244 KB Output is correct
15 Correct 18 ms 21424 KB Output is correct
16 Correct 20 ms 25436 KB Output is correct
17 Correct 8 ms 13144 KB Output is correct
18 Correct 13 ms 17192 KB Output is correct
19 Correct 16 ms 21340 KB Output is correct
20 Correct 20 ms 25180 KB Output is correct
21 Correct 8 ms 13148 KB Output is correct
22 Correct 14 ms 17212 KB Output is correct
23 Correct 17 ms 21232 KB Output is correct
24 Correct 21 ms 25176 KB Output is correct
25 Correct 660 ms 504656 KB Output is correct
26 Runtime error 690 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -