oj.uz

Submission #1087823

# Submission time Handle Problem Language Result Execution time Memory
1087823 2024-09-13T09:29:40 Z MinhKien Klasika (COCI20_klasika) C++17
110 / 110
 1705 ms 446032 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define all(v) v.begin(), v.end()
#define int long long

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef tuple<string, int, int> query;

const int N = 2e5 + 3;
const int LIM = 2;

struct node {
    set<int> jikan;
    node* children[LIM];
};

int q, n = 1;
int child[N];
query queries[N];
vector<ii> adj[N];

int timer = 0;
int h[N], d[N], tin[N], tout[N];
node *root = new node();

void prepare() {

}

void input() {
    cin >> q;

    for(int i = 1; i <= q; i++) {
        string s; int a, b; cin >> s >> a >> b;
        queries[i] = query(s, a, b);
        if(s[0] == 'A') {
            adj[a].push_back(ii(++n, b));
            child[i] = n;
        }
    }
}

void dfs(int u) {
    tin[u] = ++timer;
    for(int i = 0; i < (int)adj[u].size(); i++) {
        int v, w; tie(v, w) = adj[u][i];
        h[v] = h[u] + 1;
        d[v] = (d[u] ^ w);
        dfs(v);
    }
    tout[u] = timer;
}

void insert(int value, int jikan) {
    node *current = root;
    for(int i = 30; i >= 0; i--) {
        int ch = ((value >> i) & 1);
        if(current -> children[ch] == nullptr) {
            current -> children[ch] = new node();
        }
        current = current -> children[ch];
        current -> jikan.insert(jikan);
    }
}

bool in(node *current, int l, int r) {
    auto it = current->jikan.lower_bound(l);
    if(it == current->jikan.end() || *it > r) return false;
    else return true;
}

int get(int value, int l, int r) {
    int ans = 0;
    node *current = root;
    for(int i = 30; i >= 0; i--) {
        int ch = ((value >> i) & 1);
        if(current -> children[1 - ch] != nullptr && in(current -> children[1 - ch], l, r)) {
            ans += (1 << i);
            current = current -> children[1 - ch];
        }else {
            current = current -> children[ch];
        }
    }
    return ans;
}

void process() {
    dfs(1);

    insert(0, 1);
    for(int i = 1; i <= q; i++) {
        string type; int a, b; tie(type, a, b) = queries[i];
        if(type[0] == 'A') insert(d[child[i]], tin[child[i]]);
        else cout << get(d[a], tin[b], tout[b]) << endl;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "kurumi"
    if(fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    prepare();

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    return 0;
}

Compilation message

klasika.cpp: In function 'int32_t main()':
klasika.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14680 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 6 ms 14940 KB Output is correct
4 Correct 6 ms 14936 KB Output is correct
5 Correct 6 ms 14560 KB Output is correct
6 Correct 9 ms 14816 KB Output is correct
7 Correct 6 ms 14940 KB Output is correct
8 Correct 7 ms 14940 KB Output is correct
9 Correct 7 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 7 ms 14936 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14680 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 6 ms 14940 KB Output is correct
4 Correct 6 ms 14936 KB Output is correct
5 Correct 6 ms 14560 KB Output is correct
6 Correct 9 ms 14816 KB Output is correct
7 Correct 6 ms 14940 KB Output is correct
8 Correct 7 ms 14940 KB Output is correct
9 Correct 7 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 7 ms 14936 KB Output is correct
13 Correct 9 ms 15960 KB Output is correct
14 Correct 10 ms 17244 KB Output is correct
15 Correct 10 ms 18372 KB Output is correct
16 Correct 12 ms 19548 KB Output is correct
17 Correct 8 ms 15708 KB Output is correct
18 Correct 10 ms 16988 KB Output is correct
19 Correct 13 ms 18268 KB Output is correct
20 Correct 11 ms 19388 KB Output is correct
21 Correct 8 ms 15964 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 11 ms 18472 KB Output is correct
24 Correct 12 ms 19548 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 132692 KB Output is correct
2 Correct 726 ms 239924 KB Output is correct
3 Correct 1028 ms 342264 KB Output is correct
4 Correct 1293 ms 445484 KB Output is correct
5 Correct 428 ms 130476 KB Output is correct
6 Correct 804 ms 234928 KB Output is correct
7 Correct 1156 ms 335188 KB Output is correct
8 Correct 1601 ms 435280 KB Output is correct
9 Correct 425 ms 130128 KB Output is correct
10 Correct 726 ms 235860 KB Output is correct
11 Correct 1038 ms 337748 KB Output is correct
12 Correct 1404 ms 437608 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14680 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 6 ms 14940 KB Output is correct
4 Correct 6 ms 14936 KB Output is correct
5 Correct 6 ms 14560 KB Output is correct
6 Correct 9 ms 14816 KB Output is correct
7 Correct 6 ms 14940 KB Output is correct
8 Correct 7 ms 14940 KB Output is correct
9 Correct 7 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 7 ms 14936 KB Output is correct
13 Correct 9 ms 15960 KB Output is correct
14 Correct 10 ms 17244 KB Output is correct
15 Correct 10 ms 18372 KB Output is correct
16 Correct 12 ms 19548 KB Output is correct
17 Correct 8 ms 15708 KB Output is correct
18 Correct 10 ms 16988 KB Output is correct
19 Correct 13 ms 18268 KB Output is correct
20 Correct 11 ms 19388 KB Output is correct
21 Correct 8 ms 15964 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 11 ms 18472 KB Output is correct
24 Correct 12 ms 19548 KB Output is correct
25 Correct 407 ms 132692 KB Output is correct
26 Correct 726 ms 239924 KB Output is correct
27 Correct 1028 ms 342264 KB Output is correct
28 Correct 1293 ms 445484 KB Output is correct
29 Correct 428 ms 130476 KB Output is correct
30 Correct 804 ms 234928 KB Output is correct
31 Correct 1156 ms 335188 KB Output is correct
32 Correct 1601 ms 435280 KB Output is correct
33 Correct 425 ms 130128 KB Output is correct
34 Correct 726 ms 235860 KB Output is correct
35 Correct 1038 ms 337748 KB Output is correct
36 Correct 1404 ms 437608 KB Output is correct
37 Correct 707 ms 133852 KB Output is correct
38 Correct 1051 ms 239696 KB Output is correct
39 Correct 1305 ms 345208 KB Output is correct
40 Correct 1607 ms 446032 KB Output is correct
41 Correct 812 ms 130856 KB Output is correct
42 Correct 1201 ms 234832 KB Output is correct
43 Correct 1509 ms 335204 KB Output is correct
44 Correct 1705 ms 434584 KB Output is correct
45 Correct 841 ms 130464 KB Output is correct
46 Correct 1272 ms 236028 KB Output is correct
47 Correct 1519 ms 336284 KB Output is correct
48 Correct 1624 ms 437552 KB Output is correct