oj.uz

Submission #965549

# Submission time Handle Problem Language Result Execution time Memory
965549 2024-04-18T20:53:40 Z dosts Klasika (COCI20_klasika) C++17
33 / 110
 1838 ms 436512 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 = 2e9,MOD = 1e9+7,B = 30;


struct Trie {
    Trie* children[2] = {NULL,NULL};
    set<int> bas;
    void insert(int x,int p) {
        Trie* cur = this;
        for (int i=30;i>=-1;i--) {
            cur->bas.insert(p);
            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,int l,int r) {
        if (bas.empty()) 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.lower_bound(l) <= r) {
                ans+=(1<<i);
                cur = cur->children[go];
            } else {
                if (!cur->children[!go]) cur->children[!go] = new Trie;
                cur = cur->children[!go];
            }
        }
        return ans;
    }

};


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);
    Trie* root = new Trie;
    root->insert(0,1);
    int curry = 1;
    for (int i=1;i<=q;i++) {
        int type = qs[i].ff;
        if (!type) {
            ++curry;
            root->insert(d[curry],tin[curry]);
        }
        else {
            auto [a,b] = qs[i].ss;
            cout << root->query(d[a],tin[b],tout[b]) << '\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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 125580 KB Output is correct
2 Correct 820 ms 232180 KB Output is correct
3 Correct 1158 ms 333928 KB Output is correct
4 Correct 1605 ms 436512 KB Output is correct
5 Correct 559 ms 124544 KB Output is correct
6 Correct 952 ms 229296 KB Output is correct
7 Correct 1367 ms 329784 KB Output is correct
8 Correct 1838 ms 430176 KB Output is correct
9 Correct 466 ms 123816 KB Output is correct
10 Correct 854 ms 229876 KB Output is correct
11 Correct 1220 ms 331876 KB Output is correct
12 Correct 1690 ms 432340 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -