oj.uz

Submission #1042362

# Submission time Handle Problem Language Result Execution time Memory
1042362 2024-08-03T01:18:12 Z khanhtb Klasika (COCI20_klasika) C++14
110 / 110
 1614 ms 408832 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll int
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
const ll inf = 1e18;
const ll base = 26;
const ll blocksz = 320;
const ll N = 2e5+8;
const ll lim = 3e6+8;
// Road to Candidate Master: 268pts left
// Target: Top 1 CHD
// Ultimate Target: VOI 202k (k = ?????)
struct node{
    ll child[2];
    node(){
        child[0] = child[1] = 0;
    }
} trie[lim];
set<ll> idx[lim];
ll nownode = 0;
void add(ll x, ll id){
    ll u = 0;
    for(ll i = 29; i >= 0; i--){
        bool k = (x>>i&1);
        if(!trie[u].child[k]){
            trie[u].child[k] = ++nownode;
            trie[nownode] = node();
        }
        u = trie[u].child[k];
        idx[u].insert(id);
    }
}
bool ok(ll u, ll l, ll r){
    auto p = idx[u].lower_bound(l);
    return (p != idx[u].end() && (*p) <= r);
}
ll query(ll x, ll l, ll r){
    ll u = 0,ans = 0;
    for(ll i = 29; i >= 0; i--){
        bool k = (x>>i&1);
        if(trie[u].child[!k] && ok(trie[u].child[!k],l,r)){
            ans |= (1<<i);
            u = trie[u].child[!k];
        }
        else u = trie[u].child[k];
    }
    return ans;
}
vpll g[N];
ll h[N],tin[N],tout[N],tdfs;
void dfs(ll u){
    tin[u] = ++tdfs;
    for(auto [v,w]:g[u]){
        if(!tin[v]) dfs(v);
    }
    tout[u] = tdfs;
}
struct info{
    char s;
    ll x,y;
};
vector<info> qr;
ll q;
void solve(){
    trie[0] = node();
    cin >> q;
    ll now = 1;
    while(q--){
        string s;
        ll x,y;
        cin >> s >> x >> y;
        qr.pb({s[0],x,y});
        if(s[0] == 'A'){
            now++;
            g[x].pb({now,y});
            h[now] = (h[x]^y);
        }
    }
    dfs(1);
    add(h[1],tin[1]);
    ll nnode = 1;
    for(auto [s,x,y]:qr){
        if(s == 'A'){
            nnode++;
            add(h[nnode],tin[nnode]);
        }
        else{
            ll ans = query(h[x],tin[y],tout[y]);
            cout << ans << '\n';
        }
    }
}
signed main(){
    if(fopen("test.inp","r")){
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    for(int tt = 1; tt <= T; ++tt){
        solve();
        cout << '\n';   
    }  
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
}

Compilation message

klasika.cpp:19:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const ll inf = 1e18;
      |                ^~~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [v,w]:g[u]){
      |              ^
klasika.cpp: In function 'void solve()':
klasika.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [s,x,y]:qr){
      |              ^
klasika.cpp: In function 'int main()':
klasika.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 169560 KB Output is correct
2 Correct 44 ms 169556 KB Output is correct
3 Correct 46 ms 169556 KB Output is correct
4 Correct 45 ms 169556 KB Output is correct
5 Correct 46 ms 169552 KB Output is correct
6 Correct 45 ms 169560 KB Output is correct
7 Correct 48 ms 169524 KB Output is correct
8 Correct 45 ms 169552 KB Output is correct
9 Correct 47 ms 169560 KB Output is correct
10 Correct 47 ms 169556 KB Output is correct
11 Correct 46 ms 169556 KB Output is correct
12 Correct 47 ms 169616 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 169560 KB Output is correct
2 Correct 44 ms 169556 KB Output is correct
3 Correct 46 ms 169556 KB Output is correct
4 Correct 45 ms 169556 KB Output is correct
5 Correct 46 ms 169552 KB Output is correct
6 Correct 45 ms 169560 KB Output is correct
7 Correct 48 ms 169524 KB Output is correct
8 Correct 45 ms 169552 KB Output is correct
9 Correct 47 ms 169560 KB Output is correct
10 Correct 47 ms 169556 KB Output is correct
11 Correct 46 ms 169556 KB Output is correct
12 Correct 47 ms 169616 KB Output is correct
13 Correct 50 ms 170064 KB Output is correct
14 Correct 51 ms 170576 KB Output is correct
15 Correct 52 ms 171348 KB Output is correct
16 Correct 46 ms 171860 KB Output is correct
17 Correct 48 ms 170064 KB Output is correct
18 Correct 50 ms 170572 KB Output is correct
19 Correct 52 ms 171092 KB Output is correct
20 Correct 48 ms 171692 KB Output is correct
21 Correct 46 ms 169976 KB Output is correct
22 Correct 50 ms 170588 KB Output is correct
23 Correct 47 ms 171096 KB Output is correct
24 Correct 50 ms 171860 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 232532 KB Output is correct
2 Correct 655 ms 291440 KB Output is correct
3 Correct 969 ms 349416 KB Output is correct
4 Correct 1244 ms 408568 KB Output is correct
5 Correct 363 ms 230876 KB Output is correct
6 Correct 759 ms 288656 KB Output is correct
7 Correct 1055 ms 345084 KB Output is correct
8 Correct 1456 ms 402576 KB Output is correct
9 Correct 373 ms 230880 KB Output is correct
10 Correct 739 ms 289120 KB Output is correct
11 Correct 996 ms 346624 KB Output is correct
12 Correct 1259 ms 403816 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 169560 KB Output is correct
2 Correct 44 ms 169556 KB Output is correct
3 Correct 46 ms 169556 KB Output is correct
4 Correct 45 ms 169556 KB Output is correct
5 Correct 46 ms 169552 KB Output is correct
6 Correct 45 ms 169560 KB Output is correct
7 Correct 48 ms 169524 KB Output is correct
8 Correct 45 ms 169552 KB Output is correct
9 Correct 47 ms 169560 KB Output is correct
10 Correct 47 ms 169556 KB Output is correct
11 Correct 46 ms 169556 KB Output is correct
12 Correct 47 ms 169616 KB Output is correct
13 Correct 50 ms 170064 KB Output is correct
14 Correct 51 ms 170576 KB Output is correct
15 Correct 52 ms 171348 KB Output is correct
16 Correct 46 ms 171860 KB Output is correct
17 Correct 48 ms 170064 KB Output is correct
18 Correct 50 ms 170572 KB Output is correct
19 Correct 52 ms 171092 KB Output is correct
20 Correct 48 ms 171692 KB Output is correct
21 Correct 46 ms 169976 KB Output is correct
22 Correct 50 ms 170588 KB Output is correct
23 Correct 47 ms 171096 KB Output is correct
24 Correct 50 ms 171860 KB Output is correct
25 Correct 383 ms 232532 KB Output is correct
26 Correct 655 ms 291440 KB Output is correct
27 Correct 969 ms 349416 KB Output is correct
28 Correct 1244 ms 408568 KB Output is correct
29 Correct 363 ms 230876 KB Output is correct
30 Correct 759 ms 288656 KB Output is correct
31 Correct 1055 ms 345084 KB Output is correct
32 Correct 1456 ms 402576 KB Output is correct
33 Correct 373 ms 230880 KB Output is correct
34 Correct 739 ms 289120 KB Output is correct
35 Correct 996 ms 346624 KB Output is correct
36 Correct 1259 ms 403816 KB Output is correct
37 Correct 618 ms 232812 KB Output is correct
38 Correct 925 ms 291328 KB Output is correct
39 Correct 1185 ms 350724 KB Output is correct
40 Correct 1426 ms 408832 KB Output is correct
41 Correct 751 ms 230884 KB Output is correct
42 Correct 1051 ms 288504 KB Output is correct
43 Correct 1336 ms 344956 KB Output is correct
44 Correct 1614 ms 402224 KB Output is correct
45 Correct 689 ms 230832 KB Output is correct
46 Correct 1097 ms 289020 KB Output is correct
47 Correct 1334 ms 345688 KB Output is correct
48 Correct 1492 ms 403708 KB Output is correct