oj.uz

Submission #770508

# Submission time Handle Problem Language Result Execution time Memory
770508 2023-07-01T11:09:16 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 72 ms 20900 KB 
#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]);
            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]);
                    }
                    else rem[A] = 0;
                }
                if(t == 2) {
                    int A = query[l][1], B = query[l][2];
                    if(Q > 2000) {
                        cout << solve(1, 0, N - 1, tin[B], out[B]) << "\n";
                        continue;
                    }
                    cout << dfs(B, par[B][0], A) << "\n";
                }
            }
            return 0;
		}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 4 ms 5460 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 3 ms 5332 KB Output is correct
24 Correct 3 ms 5364 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 20900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 4 ms 5460 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 3 ms 5332 KB Output is correct
24 Correct 3 ms 5364 KB Output is correct
25 Incorrect 72 ms 20900 KB Output isn't correct
26 Halted 0 ms 0 KB -