oj.uz

Submission #930767

# Submission time Handle Problem Language Result Execution time Memory
930767 2024-02-20T11:44:34 Z Whisper Klasika (COCI20_klasika) C++17
110 / 110
 2039 ms 444640 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int numQuery;
vector<pii> adj[MAX];
struct Queries{
    string c; int a, b;
    Queries(){}
    Queries(string _c, int _a, int _b): c(_c), a(_a), b(_b){}
} qs[MAX];
struct Node{
    Node *child[2];
    set<int> passedNode;
    Node(){
        child[0] = child[1] = nullptr;
        passedNode.clear();
    }
};
Node *root = new Node();
int tin[MAX], tout[MAX], f[MAX], cnt = 0;
void dfs(int u, int p){
    tin[u] = ++cnt;
    for (pair<int, int> x : adj[u]){
        int v = x.first, w = x.second;
        f[v] = (f[u] ^ w);
        if (v ^ p){
            dfs(v, u);
        }
    }
    tout[u] = cnt;
}

void Add(int node){
    Node *p = root;
    int x = f[node];
    REPD(i, 31){
        int nxt = BIT(x, i);
        if (p -> child[nxt] == nullptr) p -> child[nxt] = new Node();
        p = p -> child[nxt];
        p -> passedNode.insert(tin[node]);
    }
    p -> passedNode.insert(tin[node]);
}
bool check(Node *p, int l, int r){
    if (p -> passedNode.empty()) return 0;
    auto g = p -> passedNode.lower_bound(l);
    if (g == p -> passedNode.end()) return 0;
    return (*g) <= r;
}
int Ask(int node, int l, int r){
    Node *p = root;
    int x = f[node];
    int ans = 0;
    REPD(i, 31){
        int nxt = BIT(x, i) ^ 1;
        if (p -> child[nxt] == nullptr || !check(p -> child[nxt], l, r)) nxt ^= 1;
        if (p -> child[nxt] == nullptr) return (ans ^ x);
        p = p -> child[nxt];
        ans |= (nxt << i);
    }
    return (ans ^ x);
}

int numNode = 1;
void Whisper(){
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++i){
        string c; int a, b;
        cin >> c >> a >> b; qs[i] = Queries(c, a, b);
        if (c == "Add"){
            ++numNode;
            adj[a].push_back({numNode, b});
            adj[numNode].push_back({a, b});
        }
    }

    dfs(1, 0);
    numNode = 1;
    Add(numNode);
    for (int i = 1; i <= numQuery; ++i){
        if (qs[i].c == "Add"){
            Add(++numNode);
        }
        else{
            cout << Ask(qs[i].a, tin[qs[i].b], tout[qs[i].b]) << '\n';
        }
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19388 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 5 ms 19292 KB Output is correct
8 Correct 4 ms 19548 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19404 KB Output is correct
11 Correct 4 ms 19292 KB Output is correct
12 Correct 5 ms 19372 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19388 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 5 ms 19292 KB Output is correct
8 Correct 4 ms 19548 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19404 KB Output is correct
11 Correct 4 ms 19292 KB Output is correct
12 Correct 5 ms 19372 KB Output is correct
13 Correct 7 ms 20316 KB Output is correct
14 Correct 7 ms 21596 KB Output is correct
15 Correct 8 ms 22872 KB Output is correct
16 Correct 9 ms 24156 KB Output is correct
17 Correct 7 ms 20316 KB Output is correct
18 Correct 8 ms 21596 KB Output is correct
19 Correct 9 ms 22956 KB Output is correct
20 Correct 10 ms 24000 KB Output is correct
21 Correct 6 ms 20372 KB Output is correct
22 Correct 8 ms 21592 KB Output is correct
23 Correct 9 ms 22876 KB Output is correct
24 Correct 11 ms 23900 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 134632 KB Output is correct
2 Correct 893 ms 240580 KB Output is correct
3 Correct 1287 ms 342260 KB Output is correct
4 Correct 1616 ms 443600 KB Output is correct
5 Correct 563 ms 133328 KB Output is correct
6 Correct 993 ms 237764 KB Output is correct
7 Correct 1375 ms 337668 KB Output is correct
8 Correct 1900 ms 437496 KB Output is correct
9 Correct 484 ms 132844 KB Output is correct
10 Correct 885 ms 238264 KB Output is correct
11 Correct 1218 ms 339936 KB Output is correct
12 Correct 1601 ms 439404 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19388 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 5 ms 19292 KB Output is correct
8 Correct 4 ms 19548 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19404 KB Output is correct
11 Correct 4 ms 19292 KB Output is correct
12 Correct 5 ms 19372 KB Output is correct
13 Correct 7 ms 20316 KB Output is correct
14 Correct 7 ms 21596 KB Output is correct
15 Correct 8 ms 22872 KB Output is correct
16 Correct 9 ms 24156 KB Output is correct
17 Correct 7 ms 20316 KB Output is correct
18 Correct 8 ms 21596 KB Output is correct
19 Correct 9 ms 22956 KB Output is correct
20 Correct 10 ms 24000 KB Output is correct
21 Correct 6 ms 20372 KB Output is correct
22 Correct 8 ms 21592 KB Output is correct
23 Correct 9 ms 22876 KB Output is correct
24 Correct 11 ms 23900 KB Output is correct
25 Correct 469 ms 134632 KB Output is correct
26 Correct 893 ms 240580 KB Output is correct
27 Correct 1287 ms 342260 KB Output is correct
28 Correct 1616 ms 443600 KB Output is correct
29 Correct 563 ms 133328 KB Output is correct
30 Correct 993 ms 237764 KB Output is correct
31 Correct 1375 ms 337668 KB Output is correct
32 Correct 1900 ms 437496 KB Output is correct
33 Correct 484 ms 132844 KB Output is correct
34 Correct 885 ms 238264 KB Output is correct
35 Correct 1218 ms 339936 KB Output is correct
36 Correct 1601 ms 439404 KB Output is correct
37 Correct 906 ms 135768 KB Output is correct
38 Correct 1332 ms 240464 KB Output is correct
39 Correct 1572 ms 344440 KB Output is correct
40 Correct 1769 ms 444640 KB Output is correct
41 Correct 950 ms 133712 KB Output is correct
42 Correct 1490 ms 237664 KB Output is correct
43 Correct 1804 ms 337632 KB Output is correct
44 Correct 2039 ms 437148 KB Output is correct
45 Correct 1004 ms 133256 KB Output is correct
46 Correct 1543 ms 238392 KB Output is correct
47 Correct 1745 ms 338260 KB Output is correct
48 Correct 1867 ms 438988 KB Output is correct