Submission #1242097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242097		Dedibeat	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4094 ms	41884 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}
int n, l, m, q;
vector<vector<int>> adj;

int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

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

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
// using node = array<int, 4>;
// node t[800005];
// inline node comb(const node &a, const node &b)
// {
//     node ans;
//     if(a[0] > b[0]) ans[0] = a[0], ans[1] = a[1];
//     else ans[0] = b[0], ans[1] = b[1];
//     if(a[2] < b[2]) ans[2] = a[2], ans[3] = a[3];
//     else ans[2] = b[2], ans[3] = b[3];
// }

// void update(int v, int tl, int tr, int pos, int new_val) {
//     if (tl == tr) {
//         t[v] = {new_val, pos, new_val, pos};
//     } else {
//         int tm = (tl + tr) / 2;
//         if (pos <= tm)
//             update(v*2, tl, tm, pos, new_val);
//         else
//             update(v*2+1, tm+1, tr, pos, new_val);
//         t[v] = comb(t[v*2], t[v*2+1]);
//     }
// }

// node query(int v, int tl, int tr, int l, int r) {
//     if (l > r) 
//         return {-1e9, -1, 1e9, -1};
//     if (l == tl && r == tr) 
//         return t[v];
//     int tm = (tl + tr) / 2;
//     return comb(query(v*2, tl, tm, l, min(r, tm)), 
//                    query(v*2+1, tm+1, tr, max(l, tm+1), r));
// }



void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    cin >> n >> m >> q;
    adj.assign(n, vector<int>());
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    preprocess(0);
    vector<int> a(m);
    for(int i = 0; i < m; i++)
        cin >> a[i], a[i]--;

    // print(tin);
    // print(a);
    while(q--)
    {
        int type;
        cin >> type;
        //cout << "q " <<  type << ": \n";
        if(type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            pos--, val--;
            a[pos] = val;
        }
        else 
        {
            int l, r, v;
            cin >> l >> r >> v;
            l--, r--, v--;
            // cout << "r :" << l << ' ' << r << '\n';
            int prev = -1, ok = 0;
            for(int i = l; i <= r; i++)
            {
                //cout << "pair " << a[prev] << " " << a[i] << "\n";
                if(a[i] == v)
                {
                    cout << i + 1 << " " << i + 1 << "\n";
                    ok = 1;
                    break;
                }
                if(prev != -1 && lca(a[prev], a[i]) == v)
                {
                    cout << prev + 1 << ' ' << i + 1 << "\n";
                    ok = 1;
                    break;
                }
                prev = i;
            }
            if(!ok) cout << "-1 -1\n";
        }

    }


}

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