Submission #1235820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235820		bach25089	Birthday gift (IZhO18_treearray)	C++20	30 / 100	4094 ms	15072 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int MAXM = 200000;
const int MAXLOG = 18;

vector<int> adj[MAXN+1];
int it[MAXN+1], ot[MAXN+1];
int dep[MAXN+1];
int pt[MAXLOG][MAXN+1];
int timer = 0;

void dfs(int u, int p, int d)
{
    it[u] = timer++;
    dep[u] = d;
    pt[0][u] = p;
    for (int v : adj[u])
    {
        if (v == p) continue;
        dfs(v, u, d+1);
    }
    ot[u] = timer-1;
}

bool oksubtree(int u, int v)
{
    return (it[v] <= it[u] && it[u] <= ot[v]);
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = MAXLOG-1; k>=0; k--)
    {
        if (d >= (1<<k))
        {
            u = pt[k][u];
            d -= (1<<k);
        }
    }
    if (u == v) return u;
    for (int k = MAXLOG-1; k>=0; k--)
    {
        if (pt[k][u] != pt[k][v])
        {
            u = pt[k][u];
            v = pt[k][v];
        }
    }
    return pt[0][u];
}

int getnode(int u, int v)
{
    if (u == v)
    {
        return 0;
    }
    int d = dep[u] - (dep[v] + 1);
    if (d < 0)
    {
        return -1;
    }
    for (int k = MAXLOG-1; k>=0; k--)
    {
        if (d >= (1<<k))
        {
            u = pt[k][u];
            d -= (1<<k);
        }
    }
    return u;
}

int a[MAXM+1];
set<int> p[MAXN+1];

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

    int n, m, q;
    cin >> n >> m >> q;

    for (int i=1; i<=n; i++)
    {
        adj[i].clear();
    }
    for (int i=0; i<n-1; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

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

    for (int k=1; k<MAXLOG; k++)
    {
        for (int i=1; i<=n; i++)
        {
            int p = pt[k-1][i];
            if (p == 0)
            {
                pt[k][i] = 0;
            }
            else
            {
                pt[k][i] = pt[k-1][p];
            }
        }
    }

    for (int i=1; i<=m; i++)
    {
        cin >> a[i];
        p[a[i]].insert(i);
    }

    for (int i=0; i<q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int pos, vl;
            cin >> pos >> vl;
            int old_val = a[pos];
            p[old_val].erase(pos);
            a[pos] = vl;
            p[vl].insert(pos);
        }
        else
        {
            int ltv, rtv, vn;
            cin >> ltv >> rtv >> vn;

            auto it = p[vn].lower_bound(ltv);
            if (it != p[vn].end() && *it <= rtv)
            {
                int pos = *it;
                cout << pos << " " << pos << "\n";
            }
            else
            {
                if (n <= 2000 && m <= 2000 && q <= 2000)
                {
                    bool fd = false;
                    for (int x = ltv; x <= rtv; x++)
                    {
                        if (!oksubtree(a[x], vn))
                        {
                            continue;
                        }
                        int sl = a[x];
                        for (int y = x; y <= rtv; y++)
                        {
                            if (!oksubtree(a[y], vn))
                            {
                                break;
                            }
                            if (y != x)
                            {
                                sl = lca(sl, a[y]);
                            }
                            if (sl == vn)
                            {
                                cout << x << " " << y << "\n";
                                fd = true;
                                break;
                            }
                        }
                        if (fd) break;
                    }
                    if (!fd)
                    {
                        cout << "-1 -1\n";
                    }
                }
                else
                {
                    int i = ltv;
                    bool fk = false;
                    while (i <= rtv)
                    {
                        if (!oksubtree(a[i], vn))
                        {
                            i++;
                            continue;
                        }
                        int j = i;
                        while (j <= rtv && oksubtree(a[j], vn))
                        {
                            j++;
                        }
                        if (j - 1 >= i + 1)
                        {
                            int branch_i = getnode(a[i], vn);
                            if (branch_i == -1)
                            {
                                i = j;
                                continue;
                            }
                            for (int k = i+1; k < min(j, i+1001); k++)
                            {
                                int branch_k = getnode(a[k], vn);
                                if (branch_k == -1)
                                {
                                    continue;
                                }
                                if (branch_k != branch_i)
                                {
                                    cout << i << " " << k << "\n";
                                    fk = true;
                                    break;
                                }
                            }
                        }
                        if (fk)
                        {
                            break;
                        }
                        i = j;
                    }
                    if (!fk)
                    {
                        cout << "-1 -1\n";
                    }
                }
            }
        }
    }

    return 0;
}

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