Submission #875164

#TimeUsernameProblemLanguageResultExecution timeMemory
875164Dr_rabi3Klasika (COCI20_klasika)C++14
0 / 110
1144 ms261648 KiB
/*** Coding for Fun ^^ وَمَا تَوْفِيقِي إِلَّا بِاللَّهِ ۚ عَلَيْهِ تَوَكَّلْتُ وَإِلَيْهِ أُنِيبُ ***/ #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> #include <ext/numeric> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ull unsigned ll #define ld long double #define ed '\n' #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fixed(x) fixed<<setprecision(x) #define memo(dp,x) memset(dp,x,sizeof(dp)) #define sumOf(a) (ll)((-1 + sqrt(8LL * a + 1)) / 2) #define debug cerr #define Good_Bay return using namespace std; using namespace __gnu_pbds; std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count()); template < typename T > using ordered_set = tree< T, null_type, less_equal< T >, rb_tree_tag, tree_order_statistics_node_update >; template < typename T > istream& operator >> (istream& in, vector < T >& v) { for (auto& x : v) in >> x; return in; } template < typename T > ostream& operator << (ostream& out, const vector < T >& v) { for (const T& x : v) out << x << ' '; return out; } void Accept() { // for VS code ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); // #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // #else // freopen("darwin.in", "r", stdin); // freopen("visitfj.out", "w", stdout); // #endif } constexpr int mod = 1e9 + 7, oo = 0x3f3f3f3f, N = 1e6 + 5; const double pi = acos(-1), EPS = 1e-7; constexpr ll OO = 0x3f3f3f3f3f3f3f3f; constexpr int dy[] = { 0 , 1 , -1 , 0 , 1 , -1 , 1 , -1 }; constexpr int dx[] = { 1 , 0 , 0 , -1 , 1 , -1 , -1 , 1 }; struct query { ll t, a, b; query(ll t, ll a, ll b) : t(t), a(a), b(b) {} }; vector<ll>adj[N]; vector<ll>in(N), out(N); vector<query>Q; ll n = 1, id = 1; void dfs(int u) { in[u] = id++; for (auto& v : adj[u]) dfs(v); out[u] = id++; } struct binary_trie { vector<array<ll, 2>> trie; vector<array<set<ll>, 2>> numsIn; int LOG; binary_trie(int _LOG) : LOG(_LOG) { trie = { array<ll, 2>{-1, -1} }; numsIn = { array<set<ll>, 2>{} }; } void insert(ll x, ll u) { int v = 0; for (int bit = LOG - 1; bit >= 0; --bit) { int to = ((1LL << bit) & x ? 1 : 0); if (~trie[v][to]) { numsIn[v][to].insert(in[u]); v = trie[v][to]; } else { numsIn[v][to].insert(in[u]); v = (trie[v][to] = (int)trie.size()); trie.push_back(array<ll, 2>{-1, -1}); numsIn.push_back(array<set<ll>, 2>{}); } } } ll query_max(ll x, ll u) { ll v = 0, sum = 0; for (int bit = LOG - 1; bit >= 0; bit--) { ll to = ((1LL << bit) & x ? 0 : 1); auto itIn = numsIn[v][to].lower_bound(in[u]); if (~trie[v][to] and itIn != numsIn[v][to].end() and *itIn <= out[u]) { v = trie[v][to], sum += to * (1LL << bit); } else { v = trie[v][1 - to]; } } return x ^ sum; } }; void doWork(int T) { int q; cin >> q; binary_trie tr(64); for (int i = 0;i < q;i++) { string s; ll a, b; cin >> s >> a >> b; if (s == "Add") { adj[a].push_back(++n); Q.push_back({ 1,a,b }); } else { Q.push_back({ 2,a,b }); } } dfs(1); vector<ll>preXor(n + 1); preXor[1] = 0; n = 1; tr.insert(0, 1); for (auto i : Q) { if (i.t == 2) cout << tr.query_max(preXor[i.a], i.b) << ed; else { preXor[++n] = preXor[i.a] ^ i.b; tr.insert(preXor[n], n); } } } int main() { // debug << "M3L4 El-Code MYTFHM4"; Accept(); int _ = 1; // cin >> _; for (int __ = 1;__ <= _;__++) { // cout << "Case " << __ << ": "; doWork(__); if (__ < _)cout << '\n'; // cout << '\n'; } Good_Bay 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...