oj.uz

Submission #338036

# Submission time Handle Problem Language Result Execution time Memory
338036 2020-12-22T10:14:57 Z arujbansal Birthday gift (IZhO18_treearray) C++17
0 / 100
 4 ms 5120 KB 
#include <bits/stdc++.h>

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5, K = 20;
int n, m, q, timer;
int a[MAXN], tin[2 * MAXN], tout[2 * MAXN], par[MAXN][K];
vector<int> g[MAXN];

void dfs(int u, int p) {
    tin[u] = timer++;

    for (int j = 1; j < K; j++)
        par[u][j] = par[par[u][j - 1]][j - 1];

    for (const auto &v : g[u]) {
        if (v == p) continue;

        par[v][0] = u;
        dfs(v, u);
    }

    tout[u] = timer++;
}

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

int query(int u, int v) {
    if (isAnc(u, v)) return u;
    if (isAnc(v, u)) return v;

    for (int j = K - 1; j >= 0; j--)
        if (!isAnc(par[u][j], v))
            u = par[u][j];

    return par[u][0];
}

void solve() {
    cin >> n >> m >> q;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    timer = 0;
    dfs(0, -1);

    set<pair<int, int>> individual;
    vector<set<int>> lca(n + 1);    

    for (int i = 0; i < m; i++) {
        cin >> a[i];
        a[i]--;

        individual.emplace(a[i], i);
    }

    for (int i = 0; i < m - 1; i++) {
        lca[query(a[i], a[i + 1])].insert(i);
    }

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

        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--, val--;

            individual.erase(make_pair(a[pos], pos));
            if (pos > 0) lca[query(a[pos], a[pos - 1])].erase(pos - 1);
            if (pos < m - 1) lca[query(a[pos], a[pos + 1])].erase(pos);

            a[pos] = val;

            individual.emplace(a[pos], pos);
            if (pos > 0) lca[query(a[pos], a[pos - 1])].insert(pos - 1);
            if (pos < m - 1) lca[query(a[pos], a[pos + 1])].insert(pos);
        } else {
            int l, r, val;
            cin >> l >> r >> val;
            l--, r--, val--;

            auto single = individual.lower_bound(make_pair(val, l));
            if (single != individual.end()) {
                int idx = (*single).second;

                if (l <= idx && idx <= r) {
                    cout << idx + 1 << " " << idx + 1 << "\n";
                    continue;
                }
            }

            auto adjacent = lca[val].lower_bound(l);
            if (adjacent == lca[val].end() || *adjacent >= r) {
                cout << "-1 -1\n";
                continue;
            }

            cout << *adjacent + 1 << " " << *adjacent + 2 << "\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Wrong range.
2 Halted 0 ms 0 KB -