Submission #338416

#	Time	Username	Problem	Language	Result	Execution time	Memory
338416		nishuz	Birthday gift (IZhO18_treearray)	C++14	30 / 100	4078 ms	876 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int mxn = 2e3+1, mxk = 15;
vector <int> adj[mxn], dep(mxn);
vector <vector <int>> par(mxn, vector <int> (mxk, -1));

void dfs(int u, int p, int d)
{
    par[u][0] = p;
    dep[u] = d;
    for (int i = 1; i < mxk; ++i)
    {
        int t = par[u][i-1];
        if (t == -1) continue;
        par[u][i] = par[t][i-1];
    }
    for (int v : adj[u])
        if (v != p)
            dfs(v, u, d+1);
}

int kthpar(int n, int k)
{
    for (int i = 0; i < mxk; ++i)
        if (k & (1 << i))
            n = par[n][i];
    return n;
}

int lca(int a, int b)
{
    if (dep[a] > dep[b]) a = kthpar(a, dep[a]-dep[b]);
    else if (dep[b] > dep[a]) b = kthpar(b, dep[b]-dep[a]);
    if (a == b) return a;
    for (int i = mxk-1; i >= 0; --i)
    {
        if (par[a][i] != par[b][i])
        {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < n-1; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector <int> a(m+1);
    for (int i = 1; i <= m; ++i) cin >> a[i];
    dfs(1, -1, 0);
    for (int Q = 0; Q < q; ++Q)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int pos, v;
            cin >> pos >> v;
            a[pos] = v;
        } else {
            int l, r, v;
            cin >> l >> r >> v;
            bool ok = 0;
            for (int i = l; i <= r; ++i)
            {
                int l = a[i];
                for (int j = i; j <= r; ++j)
                {
                    l = lca(l, a[j]);
                    if (l == v && !ok)
                    {
                        ok = 1;
                        cout << i << " " << j << '\n';
                        break;
                    }
                }
                if (ok) break;
            }
            if (!ok) cout << "-1 -1\n";
        }
    }
}

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