oj.uz

답안 #1114373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114373 2024-11-18T17:14:17 Z tintingyn21 Klasika (COCI20_klasika) C++17
33 / 110
 713 ms 524288 KB 

// author : daohuyenchi



#ifdef LOCAL
    #include "D:\C++ Submit\debug.h"
#else
    #define debug(...)
#endif



#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define db double
#define i32 int32_t  
#define i64 int64_t 
#define ll long long
// 
#define fi first
#define se second


//                                      #define int long long    // consider carefully


//
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll> 
#define PAIR make_pair 
//                                      TIME IS LIMITED ...  
#define  rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define repd(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define repv(v, H) for(auto &v: H)
//                                      REFLECT ON THE PAST ...
#define RESET(c, x) memset(c, x, sizeof(c))
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define ONBIT(mask, i) ((mask) | (1LL << (i)))
#define OFFBIT(mask, i) ((mask) &~ (1LL << (i)))
#define COUNTBIT __builtin_popcountll
//                                      30 / 1 / 2024 ? love is zero... start from zero 
#define vi vector <int>
#define vll vector <ll>
#define lwb lower_bound
#define upb upper_bound
#define all(v) (v).begin(), (v).end()
#define special(H) (H).resize(distance(H.begin(), unique(all(H))))
//                                      
#define sp ' ' 
#define nl '\n'
#define EL {cerr << '\n';}
#define yes "YES"
#define no "NO"
#define Log2(n) (63 - __builtin_clzll(n))
#define left __left__
#define right __right__ 
#define lps(id) ((id) << 1)
#define rps(id) ((id) << 1 | 1)

//____________________________________________________________________


template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

template <class... T>
void print(T&&... n) {
    using exp = int[];
    exp{0, (cerr << n << sp, 0)...};
    cerr << nl;
}

template <class T, class... C>
void assign(int n, T v, C&&... a) {
    using e = int[];
    e{(a.assign(n, v), 0)...};
}

template <class... C>
void resize(int n, C&&... a) {
    using e = int[];
    e{(a.resize(n), 0)...};
}

template <class T>
using vector2d = vector<vector<T>>;
template <class T>
using vector3d = vector<vector2d<T>>;

template <class T> int ssize(T &a) { return (int) a.size(); }


//____________________________________________________________________


mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

const int MOD      = 1000000007;
// const int MOD[2] = {1000000009, 998244353};

template<class X> void modmize(X &x, int cur_Mod = MOD) {
    if(x >= cur_Mod) x -= cur_Mod;
    if(x < 0) x += cur_Mod;
}

const long long oo = 1e18 + 7;
const long long LINF = 1e18 + 7;
const int IINF      = 2e9;
const int nmax     = 2e5 + 10;
const int MAX      = 2e5;
const int base     = 311;
const db eps       = 1e-6;
const int block    = 500;
static const double PI = acos(-1.0);

//____________________________________________________________________


int n, Q;
vector <pii> G[nmax];

array <int, 3> qs[nmax];

int pf[nmax];
int par[nmax][22], dep[nmax];
int ein[nmax], tour[nmax], eout[nmax];
int timer = 0;
void dfs(int u, int p) {
    par[u][0] = p;
    rep (k, 1, 18) {
        par[u][k] = par[par[u][k - 1]][k - 1];
    }
    dep[u] = dep[p] + 1;
    ein[u] = ++timer;
    tour[timer] = u;
    repv (e, G[u]) {
        int v = e.se;
        int w = e.fi;
        if (v == p) continue;
        pf[v] = pf[u] ^ w;
        dfs(v, u);
    }
    eout[u] = timer;
}

int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    repd (k, 18, 0) if (BIT(d, k) == 1) u = par[u][k];
    if (u == v) return u;
    repd (k, 18, 0) {
        if (par[u][k] != par[v][k]) {
            u = par[u][k];
            v = par[v][k];
        }
    }
    return par[u][0];
}

struct Node {
    int child[2];
    int cnt = 0;
    Node() {
        cnt = 0;
        rep (i, 0, 1) child[i] = -1;
    }
} ;

struct Trie {

    vector <Node> t;
    Trie() {
        assign(1, Node(), t);
        rep (k, 0, 1) {
            // assert(t[0].child[k] == -1);
        }
    }

    int new_node() {
        t.push_back(Node());
        // assert(ssize(t) > 1);
        return ssize(t) - 1;
    }    

    bool check_exist(int cur) {
        return cur != -1 && t[cur].cnt > 0;
    }

    void add(int x) {
        int cur = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            if (t[cur].child[k] == -1) {
                t[cur].child[k] = ssize(t);
                t.push_back(Node());
                // print(t[cur].child[k], ssize(t) - 1);
            }
            // print(i, cur);
            cur = t[cur].child[k];
            t[cur].cnt++;
        }
    }

    void del(int x) {
        int cur = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            cur = t[cur].child[k];
            // assert(cur != -1);
            t[cur].cnt--;
        }
    }

    int get_xor(int x) {
        int cur = 0;
        int ans = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            if (check_exist(t[cur].child[k ^ 1])) {
                ans |= 1 << i;
                cur = t[cur].child[k ^ 1];
            }
            else if (check_exist(t[cur].child[k])) {
                cur = t[cur].child[k];
            }
            else break;
        }
        return ans;
    }

} st[nmax * 4];

vector <int> sav[nmax * 4];

void build(int id, int l, int r) {
    // debug(id, l, r);
    if (l == r) {
        sav[id].push_back(pf[tour[l]]);
    }
    else {
        int mid = (l + r) / 2;
        build(lps(id), l, mid);
        build(rps(id), mid + 1, r);
        merge(sav[lps(id)].begin(), sav[lps(id)].end(), sav[rps(id)].begin(), sav[rps(id)].end(), back_inserter(sav[id]));
    }

    repv (v, sav[id]) st[id].add(v);

}

void upd(int id, int l, int r, int i, int val) {
    if (l > i || r < i) return;
    st[id].del(val);
    if (l == r) return;
    int mid = (l + r) / 2;
    upd(lps(id), l, mid, i, val);
    upd(rps(id), mid + 1, r, i, val);
}

int get(int id, int l, int r, int u, int v, int val) {
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) {
        return st[id].get_xor(val);
    }
    int mid = (l + r) / 2;
    return max(get(lps(id), l, mid, u, v, val), get(rps(id), mid + 1, r, u, v, val));
}

void tintingyn() {

    cin >> Q;
    n = 1;
    rep (i, 0, Q - 1) {
        string type;
        int x, y;
        cin >> type >> x >> y;
        int t = type == "Add" ? 0 : 1;
        qs[i] = {t, x, (t == 0 ? n + 1 : y)};
        if (t == 0) G[x].push_back({y, ++n});
    }
    
    dfs(1, 0);

    // rep (i, 1, n) debug(ein[i], pf[i]);    
    build(1, 1, n);

    // return ;

    vector <int> ans(Q);
    repd (_i, Q - 1, 0) {
        auto &tv = qs[_i];
        // print(tv[0]);
        if (tv[0] == 1) {
            int u = tv[1];
            int v = tv[2];
            // debug(u, v);
            ans[_i] = get(1, 1, n, ein[v], eout[v], pf[u]);
        }
        else {
            int u = tv[1];
            int v = tv[2];
            upd(1, 1, n, ein[v], pf[v]);
        }
    }

    rep (i, 0, Q - 1) {
        auto &tv = qs[i];
        if (tv[0] == 1) cout << ans[i] << nl;
    }

}

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

    //________________________________________________________________

    #define TASK "3"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    //________________________________________________________________
    
    //  CODE FROM HERE ...! 





    int num_test = 1; 
    // cin >> num_test;

    while(num_test--) {

        tintingyn();

    }


    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" << nl;

    return 0;
}

Compilation message

klasika.cpp: In function 'void tintingyn()':
klasika.cpp:315:17: warning: unused variable 'u' [-Wunused-variable]
  315 |             int u = tv[1];
      |                 ^
klasika.cpp: In function 'int main()':
klasika.cpp:337:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  337 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:338:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  338 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 70728 KB Output is correct
2 Correct 69 ms 69448 KB Output is correct
3 Correct 65 ms 73544 KB Output is correct
4 Correct 60 ms 69716 KB Output is correct
5 Correct 49 ms 70728 KB Output is correct
6 Correct 56 ms 69400 KB Output is correct
7 Correct 63 ms 69448 KB Output is correct
8 Correct 61 ms 69848 KB Output is correct
9 Correct 65 ms 69192 KB Output is correct
10 Correct 56 ms 69456 KB Output is correct
11 Correct 61 ms 69464 KB Output is correct
12 Correct 62 ms 69704 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 70728 KB Output is correct
2 Correct 69 ms 69448 KB Output is correct
3 Correct 65 ms 73544 KB Output is correct
4 Correct 60 ms 69716 KB Output is correct
5 Correct 49 ms 70728 KB Output is correct
6 Correct 56 ms 69400 KB Output is correct
7 Correct 63 ms 69448 KB Output is correct
8 Correct 61 ms 69848 KB Output is correct
9 Correct 65 ms 69192 KB Output is correct
10 Correct 56 ms 69456 KB Output is correct
11 Correct 61 ms 69464 KB Output is correct
12 Correct 62 ms 69704 KB Output is correct
13 Correct 66 ms 71072 KB Output is correct
14 Correct 68 ms 73100 KB Output is correct
15 Correct 69 ms 75092 KB Output is correct
16 Correct 82 ms 77364 KB Output is correct
17 Correct 64 ms 70984 KB Output is correct
18 Correct 66 ms 72960 KB Output is correct
19 Correct 70 ms 74808 KB Output is correct
20 Correct 82 ms 76852 KB Output is correct
21 Correct 72 ms 70984 KB Output is correct
22 Correct 77 ms 73016 KB Output is correct
23 Correct 69 ms 74836 KB Output is correct
24 Correct 78 ms 76880 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 713 ms 312284 KB Output is correct
2 Runtime error 670 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 70728 KB Output is correct
2 Correct 69 ms 69448 KB Output is correct
3 Correct 65 ms 73544 KB Output is correct
4 Correct 60 ms 69716 KB Output is correct
5 Correct 49 ms 70728 KB Output is correct
6 Correct 56 ms 69400 KB Output is correct
7 Correct 63 ms 69448 KB Output is correct
8 Correct 61 ms 69848 KB Output is correct
9 Correct 65 ms 69192 KB Output is correct
10 Correct 56 ms 69456 KB Output is correct
11 Correct 61 ms 69464 KB Output is correct
12 Correct 62 ms 69704 KB Output is correct
13 Correct 66 ms 71072 KB Output is correct
14 Correct 68 ms 73100 KB Output is correct
15 Correct 69 ms 75092 KB Output is correct
16 Correct 82 ms 77364 KB Output is correct
17 Correct 64 ms 70984 KB Output is correct
18 Correct 66 ms 72960 KB Output is correct
19 Correct 70 ms 74808 KB Output is correct
20 Correct 82 ms 76852 KB Output is correct
21 Correct 72 ms 70984 KB Output is correct
22 Correct 77 ms 73016 KB Output is correct
23 Correct 69 ms 74836 KB Output is correct
24 Correct 78 ms 76880 KB Output is correct
25 Correct 713 ms 312284 KB Output is correct
26 Runtime error 670 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -