oj.uz

Submission #1100256

# Submission time Handle Problem Language Result Execution time Memory
1100256 2024-10-13T10:57:38 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
0 / 100
 2 ms 11088 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 200002;
const int lo = 18;

int n, m, q;
vector<int> t[maxn];
int parent[maxn][lo];
int depth[maxn];
int tin[maxn], tout[maxn], timer = 0;
vector<int> a;

void dfs(int v, int p) {
    tin[v] = timer++;
    parent[v][0] = p;
    for (int i = 1; i < lo; i++) {
        parent[v][i] = parent[parent[v][i - 1]][i - 1];
    }
    for (int u : t[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}

bool is_ancestor(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = lo - 1; i >= 0; --i) {
        if (!is_ancestor(parent[u][i], v)) {
            u = parent[u][i];
        }
    }
    return parent[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> q;
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        t[u].pb(v);
        t[v].pb(u);
    }

    dfs(1, 1);
    
    a.resize(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int pos, v;
            cin >> pos >> v;
            a[pos] = v;
        } else if (type == 2) {
            int l, r, v;
            cin >> l >> r >> v;

            int current_lca = a[l];
            bool found = false;

            for (int i = l; i <= r; i++) {
                current_lca = lca(current_lca, a[i]);
                if (current_lca == v) {
                    cout << l << " " << i << endl;
                    found = true;
                    break;
                }
            }

            if (!found) {
                cout << -1 << " " << -1 << endl;
            }
        }
    }

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11088 KB n=5
2 Incorrect 2 ms 11088 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11088 KB n=5
2 Incorrect 2 ms 11088 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11088 KB n=5
2 Incorrect 2 ms 11088 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11088 KB n=5
2 Incorrect 2 ms 11088 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -