제출 #1317871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317871		hrantsargsyan	Birthday gift (IZhO18_treearray)	C++20	100 / 100	990 ms	83616 KiB

treearray

#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

vector<int> a;
const int N = 2e5 + 5;
const int LOG = 25;
int m;
vector<int> adj[N];
int up[N][LOG];
int dept[N];
set<int> lcas1[N];
set<int> lcas2[N];



void dfs(int node, int parent)
{
    for (auto i : adj[node])
    {
        if (i == parent)
            continue;
        up[i][0] = node;
        for (int j = 1;j < LOG;++j)
        {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
        dept[i] = dept[node] + 1;
        dfs(i, node);
    }
}

int lift(int a, int k)
{
    for (int j = LOG - 1;j >= 0;--j)
    {
        if (k & (1 << j))
        {
            a = up[a][j];
        }
    }
    return a;
}

int lca(int a, int b)
{
    if (a == b)
        return a;
    if (dept[a] < dept[b])
    {
        swap(a, b);
    }
    int dif = dept[a] - dept[b];
    a = lift(a, dif);
    if (a == b)
        return a;
    for (int j = LOG - 1;j >= 0;--j)
    {
        if (up[a][j] != up[b][j])
        {
            a = up[a][j];
            b = up[b][j];
        }
    }
    return up[a][0];
}


int main()
{
    int n, q;
    cin >> n >> m >> q;
    for (int i = 0;i < n - 1;++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dept[1] = 0;
    dfs(1, 0);
    for (int i = 0;i < m;++i)
    {
        int x;
        cin >> x;
        a.push_back(x);
        lcas1[x].insert(i);
    }
    for (int i = 0;i < m-1;++i)
    {
        lcas2[lca(a[i], a[i+1])].insert(i);
    }
    for (int i = 0;i < q;++i)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int ind, v;
            cin >> ind >> v;
            --ind;
            lcas1[a[ind]].erase(ind);
            lcas1[v].insert(ind);
            if (ind < m - 1)
            {
                lcas2[lca(a[ind], a[ind + 1])].erase(ind);
                lcas2[lca(v, a[ind + 1])].insert(ind);
            }
            if (ind > 0)
            {
                lcas2[lca(a[ind - 1], a[ind])].erase(ind - 1);
                lcas2[lca(a[ind - 1], v)].insert(ind - 1);
            }
            a[ind] = v;        
        }
        else if (type == 2)
        {
            int l, r, v;
            cin >> l >> r >> v;
            --l;
            --r;
            auto it = lcas1[v].lower_bound(l);
            if (it != lcas1[v].end() && *it<=r)
            {
                cout << *it + 1 << " " << *it + 1 << endl;
            }
            else
            {
                it = lcas2[v].lower_bound(l);
                if (it != lcas2[v].end() && *it<=r-1)
                {
                    cout << *it+1 << " " << *it + 2 << endl;
                }
                else
                {
                    cout << -1 << " " << -1 << endl;
                }
            }
        }
    }
}

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