Submission #875175

#TimeUsernameProblemLanguageResultExecution timeMemory
875175Dr_rabi3Klasika (COCI20_klasika)C++14
0 / 110
1818 ms524288 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 }; vector<int>adj[N]; vector<int>in(N), out(N); int id = 1; void dfs(int u) { in[u] = id++; for (auto v : adj[u])dfs(v); out[u] = id++; } struct binary_trie { vector<array<int, 2>> trie; vector<array<set<int>, 2>>tin; int LOG; binary_trie(int _LOG) : LOG(_LOG) { trie = { array<int, 2>{-1, -1} }; tin = { array<set<int>, 2>{} }; } void insert(int x, int u) { int v = 0; for (int bit = LOG - 1; bit >= 0; --bit) { int to = ((1 << bit) & x ? 1 : 0); if (~trie[v][to]) { tin[v][to].insert(in[u]); v = trie[v][to]; } else { tin[v][to].insert(in[u]); v = (trie[v][to] = (int)trie.size()); trie.push_back(array<int, 2>{-1, -1}); tin.push_back(array<set<int>, 2>{}); } } } int query_max(int x, int u) { int v = 0, sum = 0; for (int bit = LOG - 1; bit >= 0; bit--) { int to = ((1 << bit) & x ? 0 : 1); if (~trie[v][to] and tin[v][to].lower_bound(in[u]) != tin[v][to].lower_bound(out[u] + 1)) { v = trie[v][to], sum += to * (1 << bit); } else v = trie[v][1 - to], sum += (1 - to) * (1 << bit); } return x ^ sum; } }; void doWork(int T) { int q, n = 1; cin >> q; vector<int>preXor(2); vector<pair<string, pair<int, int>>>Q(q); for (auto& i : Q) { cin >> i.first >> i.second.first >> i.second.second; if (i.first == "Add") { adj[i.second.first].push_back(++n); preXor.push_back(preXor[i.second.first] ^ i.second.second); } } dfs(1); binary_trie tr(32); tr.insert(0, 1); n = 1; for (auto i : Q) { if (i.first == "Add") tr.insert(preXor[++n], n); else cout << tr.query_max(preXor[i.second.first], i.second.second) << ed; } } 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; }

Compilation message (stderr)

klasika.cpp: In function 'void doWork(int)':
klasika.cpp:125:48: warning: operation on 'n' may be undefined [-Wsequence-point]
  125 |         if (i.first == "Add") tr.insert(preXor[++n], n);
      |                                                ^~~
klasika.cpp:125:48: warning: operation on 'n' may be undefined [-Wsequence-point]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...