Submission #770580

#	Time	Username	Problem	Language	Result	Execution time	Memory
770580		MohamedFaresNebili	Klasika (COCI20_klasika)	C++14	33 / 110	732 ms	46016 KiB

klasika

#include <bits/stdc++.h>

		using namespace std;

		int Q, N = 1, cur[200005];
		int ST[800005], par[200005][20], calc[200005][20];
		int timer, tin[200005], out[200005];
		bool rem[200005];
		vector<pair<int, int>> adj[200005];

		void update(int v, int l, int r, int p, int val) {
            if(l == r) {
                ST[v] = val;
                return;
            }
            int md = (l + r) / 2;
            if(p <= md) update(v * 2, l, md, p, val);
            else update(v * 2 + 1, md + 1, r, p, val);
            ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
		}
		int solve(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return 0;
            if(l >= lo && r <= hi) return ST[v];
            return max(solve(v * 2, l, (l + r) / 2, lo, hi),
                solve(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
		}
		void dfs(int v, int p) {
            tin[v] = timer++; par[v][0] = p;
            for(auto u : adj[v]) {
                if(u.first == p) continue;
                cur[u.first] = (cur[v] ^ u.second);
                calc[u.first][0] = u.second;
                rem[u.first] = 1; dfs(u.first, v);
            }
            out[v] = timer - 1;
		}
		int dfs(int v, int p, int t) {
            int best = (cur[v] ^ cur[t]);
            for(auto u : adj[v]) {
                if(u.first == p || rem[u.first]) continue;
                best = max(best, dfs(u.first, v, t));
            }
            return best;
		}

		int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> Q;
            vector<array<int, 4>> query;
            for(int l = 0; l < Q; l++) {
                string S; int A, B;
                cin >> S >> A >> B;
                if(S == "Add") {
                    ++N; adj[A].push_back({N, B});
                    adj[N].push_back({A, B});
                    query.push_back({1, A, N, B});
                }
                if(S == "Query")
                    query.push_back({2, A, B});
            }
            dfs(1, 1);
            for(int l = 1; l < 20; l++)
                for(int i = 1; i <= N; i++)
                    par[i][l] = par[par[i][l - 1]][l - 1],
                    calc[i][l] = (calc[i][l - 1] ^ calc[par[i][l - 1]][l - 1]);
            map<int, int> M; int var = 0;
            for(int i = 30; i >= 0; i--) {
                if(cur[1] & (1 << i))
                    var += (1 << i);
                M[var] = 2;
            }
            M[var] = 1;
            for(int l = 0; l < Q; l++) {
                int t = query[l][0];
                if(t == 1) {
                    int A = query[l][2];
                    if(Q > 2000) {
                        /// update(1, 0, N - 1, tin[A], cur[A]);
                        int K = 0;
                        for(int i = 30; i >= 0; i--) {
                            if(cur[A] & (1 << i))
                                K += (1 << i);
                            M[K] = 2;
                        }
                        M[K] = 1;
                    }
                    else rem[A] = 0;
                }
                if(t == 2) {
                    int A = query[l][1], B = query[l][2];
                    if(Q > 2000) {
                        int res = 0;
                        for(int i = 30; i >= 0; i--) {
                            if((cur[A] & (1 << i)) == 0) {
                                res += (1 << i);
                                if(M[res] == 0)
                                    res -= (1 << i);
                            }
                            else {
                                if(M[res] == 0)
                                    res += (1 << i);
                            }
                        }
                        cout << res << "\n";
                        continue;
                    }
                    cout << dfs(B, par[B][0], A) << "\n";
                }
            }
            return 0;
		}

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