Submission #1128677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128677		_callmelucian	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4094 ms	25388 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
int sz[mn], chain[mn], depth[mn], par[mn], arr[mn];
vector<int> adj[mn];

int szDfs (int u, int p) {
    sz[u] = 1;
    for (int v : adj[u])
        if (v != p) sz[u] += szDfs(v, u);
    return sz[u];
}

void dfs (int u, int p, int d, bool toP) {
    if (u == 1) szDfs(u, p);
    chain[u] = (toP ? chain[p] : u);
    depth[u] = d, par[u] = p;
    sort(all(adj[u]), [&] (int a, int b) {
            return sz[a] > sz[b];
         });
    bool heavy = 1;
    for (int v : adj[u])
        if (v != p) dfs(v, u, d + 1, heavy), heavy = 0;
}

int lca (int a, int b) {
    if (min(a, b) == 0) return max(a, b);
    while (chain[a] != chain[b]) {
        int ap = par[chain[a]], bp = par[chain[b]];
        if (depth[ap] == depth[bp]) a = ap, b = bp;
        else if (depth[ap] > depth[bp]) a = ap;
        else if (depth[bp] > depth[ap]) b = bp;
    }
    return (depth[a] < depth[b] ? a : b);
}

struct IT {
    vector<int> tr;
    IT (int sz) : tr(4 * sz) {}

    void update (int pos, int node, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }
        tr[k] = node;
        for (k >>= 1; k; k >>= 1)
            tr[k] = lca(tr[k << 1], tr[k << 1 | 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return lca(query(a, b, k << 1, l, mid),
                   query(a, b, k << 1 | 1, mid + 1, r));
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0, 1, 0);

    IT tree(m);
    for (int i = 1; i <= m; i++) {
        int a; cin >> a;
        tree.update(i, a, 1, 1, m);
    }

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int pos, v; cin >> pos >> v;
            tree.update(pos, v, 1, 1, m);
        }
        else {
            int l, r, v; cin >> l >> r >> v;
            bool flag = 0;
            for (int x = l, y = l - 1; x <= r; x++) {
                y = max(y, x - 1);
                while (y + 1 <= r && depth[tree.query(x, y + 1, 1, 1, m)] > depth[v]) y++;
                if (y + 1 <= r && tree.query(x, y + 1, 1, 1, m) == v) {
                    cout << x << " " << y + 1 << "\n";
                    flag = 1; break;
                }
            }
            if (!flag) cout << "-1 -1\n";
        }
    }

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44