Submission #875156

#TimeUsernameProblemLanguageResultExecution timeMemory
875156Dr_rabi3Klasika (COCI20_klasika)C++14
0 / 110
930 ms107740 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 = 2e5 + 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 { int t, a, b; }; vector<int>adj[N]; vector<int>in(N), out(N); vector<query>Q; int 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<int, 2>> trie; vector<array<set<int>, 2>> numsIn; int LOG; binary_trie(int _LOG) : LOG(_LOG) { trie = { array<int, 2>{-1, -1} }; numsIn = { array<set<int>, 2>{} }; } void insert(int x, int 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<int, 2>{-1, -1}); numsIn.push_back(array<set<int>, 2>{}); } } } ll query_max(ll x, int u) { ll v = 0, sum = 0; for (int bit = LOG - 1; bit >= 0; bit--) { ll to = ((1LL << bit) & x ? 0 : 1); if (~trie[v][to]) { auto itIn = numsIn[v][to].lower_bound(in[u]); if (itIn != numsIn[v][to].end() and *itIn <= out[u]) { v = trie[v][to], sum += to * (1LL << bit); } else v = trie[v][1 - to], sum += (1 - to) * (1LL << bit); } else { v = trie[v][1 - to], sum += (1 - to) * (1LL << bit); } } return x ^ sum; } }; void doWork(int T) { int q; cin >> q; binary_trie tr(32); vector<int>preXor(N); for (int i = 0;i < q;i++) { string s; int a, b; cin >> s >> a >> b; if (s == "Add") { adj[a].push_back(++n); preXor[n] = preXor[a] ^ b; Q.push_back({ 1,a,b }); } else { Q.push_back({ 2,a,b }); } } dfs(1); 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 { 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; }

Compilation message (stderr)

klasika.cpp: In function 'void doWork(int)':
klasika.cpp:142:30: warning: operation on 'n' may be undefined [-Wsequence-point]
  142 |             tr.insert(preXor[++n], n);
      |                              ^~~
klasika.cpp:142:30: warning: operation on 'n' may be undefined [-Wsequence-point]
klasika.cpp: In function 'void Accept()':
klasika.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...