oj.uz

Submission #1087724

# Submission time Handle Problem Language Result Execution time Memory
1087724 2024-09-13T06:57:38 Z shidou26 Klasika (COCI20_klasika) C++14
110 / 110
 1822 ms 446108 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 6 ms 14684 KB Output is correct
2 Correct 9 ms 14684 KB Output is correct
3 Correct 6 ms 14928 KB Output is correct
4 Correct 8 ms 14936 KB Output is correct
5 Correct 8 ms 14524 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14816 KB Output is correct
8 Correct 6 ms 14940 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 6 ms 15192 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 9 ms 14684 KB Output is correct
3 Correct 6 ms 14928 KB Output is correct
4 Correct 8 ms 14936 KB Output is correct
5 Correct 8 ms 14524 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14816 KB Output is correct
8 Correct 6 ms 14940 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 6 ms 15192 KB Output is correct
13 Correct 8 ms 15960 KB Output is correct
14 Correct 10 ms 17112 KB Output is correct
15 Correct 11 ms 18524 KB Output is correct
16 Correct 11 ms 19548 KB Output is correct
17 Correct 9 ms 15708 KB Output is correct
18 Correct 13 ms 16988 KB Output is correct
19 Correct 10 ms 18268 KB Output is correct
20 Correct 11 ms 19544 KB Output is correct
21 Correct 10 ms 15708 KB Output is correct
22 Correct 8 ms 17176 KB Output is correct
23 Correct 10 ms 18416 KB Output is correct
24 Correct 13 ms 19548 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 130068 KB Output is correct
2 Correct 683 ms 239696 KB Output is correct
3 Correct 1047 ms 342320 KB Output is correct
4 Correct 1304 ms 445508 KB Output is correct
5 Correct 425 ms 130276 KB Output is correct
6 Correct 833 ms 234872 KB Output is correct
7 Correct 1210 ms 335168 KB Output is correct
8 Correct 1567 ms 435284 KB Output is correct
9 Correct 457 ms 130128 KB Output is correct
10 Correct 757 ms 235860 KB Output is correct
11 Correct 1014 ms 337764 KB Output is correct
12 Correct 1358 ms 437552 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 9 ms 14684 KB Output is correct
3 Correct 6 ms 14928 KB Output is correct
4 Correct 8 ms 14936 KB Output is correct
5 Correct 8 ms 14524 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14816 KB Output is correct
8 Correct 6 ms 14940 KB Output is correct
9 Correct 5 ms 14684 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 6 ms 15192 KB Output is correct
13 Correct 8 ms 15960 KB Output is correct
14 Correct 10 ms 17112 KB Output is correct
15 Correct 11 ms 18524 KB Output is correct
16 Correct 11 ms 19548 KB Output is correct
17 Correct 9 ms 15708 KB Output is correct
18 Correct 13 ms 16988 KB Output is correct
19 Correct 10 ms 18268 KB Output is correct
20 Correct 11 ms 19544 KB Output is correct
21 Correct 10 ms 15708 KB Output is correct
22 Correct 8 ms 17176 KB Output is correct
23 Correct 10 ms 18416 KB Output is correct
24 Correct 13 ms 19548 KB Output is correct
25 Correct 391 ms 130068 KB Output is correct
26 Correct 683 ms 239696 KB Output is correct
27 Correct 1047 ms 342320 KB Output is correct
28 Correct 1304 ms 445508 KB Output is correct
29 Correct 425 ms 130276 KB Output is correct
30 Correct 833 ms 234872 KB Output is correct
31 Correct 1210 ms 335168 KB Output is correct
32 Correct 1567 ms 435284 KB Output is correct
33 Correct 457 ms 130128 KB Output is correct
34 Correct 757 ms 235860 KB Output is correct
35 Correct 1014 ms 337764 KB Output is correct
36 Correct 1358 ms 437552 KB Output is correct
37 Correct 724 ms 133932 KB Output is correct
38 Correct 1037 ms 239784 KB Output is correct
39 Correct 1372 ms 345148 KB Output is correct
40 Correct 1591 ms 446108 KB Output is correct
41 Correct 840 ms 130896 KB Output is correct
42 Correct 1294 ms 234916 KB Output is correct
43 Correct 1525 ms 335188 KB Output is correct
44 Correct 1822 ms 434572 KB Output is correct
45 Correct 835 ms 130484 KB Output is correct
46 Correct 1292 ms 235860 KB Output is correct
47 Correct 1601 ms 336328 KB Output is correct
48 Correct 1721 ms 437524 KB Output is correct