oj.uz

Submission #1100240

# Submission time Handle Problem Language Result Execution time Memory
1100240 2024-10-13T10:42:40 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
0 / 100
 3 ms 10492 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 200002;
const int lo = 17;
int n, m, q;
vector<int> t[maxn];
int parent[maxn][lo];
int deep[maxn];
int tin[maxn],tout[maxn],timer=0;

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) {
            deep[u] = deep[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}
bool anc(int v, int u) {
    return tin[v]<= tin[u] && tout[v] >= tout[u];
}
int lca(int u, int v) {
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    for (int i = lo-1; i >= 0; i--) {
        if (!anc(parent[u][i], v)) {
            u = parent[u][i];
        }
    }
    return parent[u][0];
}
int main() {
    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);
    vector<int> a(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 currlca = a[l];
            bool found = false;
            for (int i = l; i<= r; i++) {
                currlca = lca(currlca, a[i]);
                if (currlca ==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 3 ms 10492 KB n=5
2 Incorrect 3 ms 10320 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 3 ms 10492 KB n=5
2 Incorrect 3 ms 10320 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 3 ms 10492 KB n=5
2 Incorrect 3 ms 10320 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 3 ms 10492 KB n=5
2 Incorrect 3 ms 10320 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -