제출 #1222937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222937		Dreamy_lovesper	Klasika (COCI20_klasika)	C++20	110 / 110	2462 ms	454484 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first 
#define se second 
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

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

// I wonder… will I just become a distant memory to you one day?
#define mxn 200'007
ll n, q;

struct Quest {
    str o; ll u, v;
} Qu[mxn];

namespace Love12 {
    bool check () {
        return ( q <= 2007 );
    }

    ll par[2007];
    vector<pll> graph[2007];
    ll sad = 0, cr = 0;
    void dfs(ll u, ll p, ll sum) {
        maximize(sad, cr ^ sum);
        for(auto&[v, w]: graph[u]) {
            if(v == p) continue;
            dfs(v, u, sum ^ w);
        }
    }

    bool findV(ll u, ll p, ll end) {
        if(u == end) return 1;
        for(auto&[v, w]: graph[u]) {
            if(v == p) continue;
            if(findV(v, u, end)) {cr ^= w; return 1;}
        }
        return 0;
    }

    void DreamyLove () {

        ll vertex = 1;
        fu(qst, 1, q) {
            auto[o, u, v] = Qu[qst];
            if(o == "Add") {
                graph[u].pb({++vertex, v});
                graph[vertex].pb({u, v});
                par[vertex] = u;
            } else {
                sad = 0, cr = 0;
                findV(u, 0, v);
                dfs(v, par[v], 0);
                cout << sad << '\n';
            }
        }
        //
    }
}

namespace Love3 {
    bool check () {
        fu(i, 1, q) if(Qu[i].o != "Add") if(Qu[i].v != 1) return 0;
        return 1;
    }

    struct Trie{

        struct Node {
            Node*child[2];
            Node () { 
                child[0] = child[1] = nullptr;
            }
        };

        Node*root;
        Trie() {root = new Node();}

        void add(ll x) {
            Node*p = root;
            fd(j, 31, 0) {
                ll k = Bitc(x, j);
                if(p->child[k] == nullptr) p->child[k] = new Node();
                p = p->child[k];
            }
        }

        ll get(ll x) {
            Node*p = root;
            ll sad = 0;
            fd(j, 31, 0) {
                ll k = Bitc(x, j);
                if(p->child[k ^ 1] != nullptr) {
                    sad |= (1 << j);
                    p = p->child[k ^ 1];
                } else if(p->child[k] != nullptr) p = p ->child[k];
                else break;
            }
            return sad;
        }

    } trie;

    ll g[mxn];
    void DreamyLove () {

        ll vertex = 1;
        trie.add(0);
        fu(qst, 1, q) {
            auto[o, u, v] = Qu[qst];
            if(o == "Add") {
                g[++vertex] = (g[u] ^ v);
                trie.add(g[vertex]);
            } else cout << trie.get(g[u]) << '\n';
        }
        //
    }
}

namespace LoveLast {

    struct Trie {
        struct Node {
            Node*child[2];
            set<ll> ids;
            Node () {
                child[0] = child[1] = nullptr;
                ids.clear();
            }
        };

        Node*root;
        Trie() {root = new Node();}
        
        void add(ll x, ll id) {
            Node*p = root;
            p->ids.insert(id);
            fd(j, 31, 0) {
                ll k = Bitc(x, j);
                if(p->child[k] == nullptr) p->child[k] = new Node();
                p = p->child[k];
                p->ids.insert(id);
            }
        }

        ll get(ll x, ll l, ll r) {
        Node*p = root;
        ll sad = 0;
        fd(j, 31, 0) {
            ll k = Bitc(x, j);
            if (p->child[k ^ 1] != nullptr) {
                if (p->child[k ^ 1]->ids.lower_bound(l) != p->child[k ^ 1]->ids.upper_bound(r)) {
                    sad |= (1 << j);
                    p = p->child[k ^ 1];
                } else if (p->child[k] != nullptr) p = p->child[k];
                else break;
            } else if (p->child[k] != nullptr) p = p->child[k];
            else break;
        }
    return sad;
}


    } trie;

    ll g[mxn], tin[mxn], tout[mxn];
    vector<pll> graph[mxn];

    void dfs(ll u, ll p, ll sum) {
        static ll time = 0;
        tin[u] = ++time; g[u] = sum;
        for(auto&[v, w]: graph[u]) {
            if(v == p) continue;
            dfs(v, u, (sum ^ w));
        }
        tout[u] = time;
    }

    void DreamyLove () {

        ll vertex = 1;
        fu(i, 1, q) {
            auto[o, u, v] = Qu[i];
            if(o == "Query") continue;
            graph[u].pb({++vertex, v});
            graph[vertex].pb({u, v});
            Qu[i].u = vertex;
        }

        dfs(1, 0, 0);
        trie.add(0, 1);
        fu(i, 1, q) {
            auto[o, u, v] = Qu[i];
            if(o == "Add") trie.add(g[u], tin[u]);
            else cout << trie.get(g[u], tin[v], tout[v]) << '\n';
        }
        //
    }
}

void lovesper(const ll &TestCase) {
    cin >> q;

    fu ( i, 1, q ) cin >> Qu[i].o >> Qu[i].u >> Qu[i].v;

    // if(Love12::check()) {
    //     Love12::DreamyLove();
    //     return;
    // }

    // if(Love3::check()) {
    //     Love3::DreamyLove();
    //     return;
    // }
    
    LoveLast::DreamyLove();

}

signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    
    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44