제출 #1176625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176625		vicvic	Birthday gift (IZhO18_treearray)	C++20	0 / 100	10 ms	23876 KiB

treearray

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int NMAX=2e5, LGMAX=18;
int in[NMAX+5], out[NMAX+5], v[NMAX+5], euler[2*NMAX+5], n, m, q, timer, depth[2*NMAX+5], t[NMAX+5], table[NMAX+5][LGMAX+1], l[NMAX+5];
vector <int> vec[NMAX+5];
set <int> poz[NMAX+5];
set <int> lcas[NMAX+5];
void dfs (int nod, int tatal=0, int d=0)
{
    t[nod]=tatal;
    table[nod][0]=t[nod];
    depth[nod]=d;
    for (int i=1;i<=LGMAX;i++)
    {
        table[nod][i]=table[table[nod][i-1]][i-1];
    }
    for (auto adj : vec[nod])
    {
        if (adj==tatal)
            continue;
        dfs (adj, nod, d+1);
    }
}
int LCA (int a, int b)
{
    if (depth[a]<depth[b])
        swap (a, b);
    int dif=depth[a]-depth[b];
    for (int i=0;i<=LGMAX;i++)
    {
        if ((1 << i) & dif)
            a=table[a][i];
    }
    if (a==b)
        return a;
    for (int i=LGMAX;i>0;i--)
    {
        if (table[a][i]!=table[b][i]) a=table[a][i], b=table[b][i];
    }
    return table[a][0];
}
void upd (int p, int val)
{
    poz[v[p]].erase (p);
    v[p]=val;
    poz[v[p]].insert (p);
    lcas[l[p-1]].erase (p-1);
    lcas[l[p]].erase (p);
    l[p]=LCA (v[p], v[p+1]);
    l[p-1]=LCA (v[p-1], v[p]);
    lcas[l[p-1]].insert (p-1);
    lcas[l[p]].insert (p);
}
void solve (int st, int dr, int nod)
{
    auto itp=poz[nod].lower_bound (st);
    auto itl=lcas[nod].lower_bound (st);
    if (itp!=poz[nod].end() && *itp<=dr) cout << *itp << " " << *itp << "\n";
    else if (itl!=lcas[nod].end() && *itl<dr) cout << *itl << " " << *itl+1 << "\n";
    else cout << "-1 -1\n";
}
int main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++)
    {
        int x, y;
        cin >> x >> y;
        vec[x].push_back (y);
        vec[y].push_back (x);
    }
    dfs (1);
    for (int i=1;i<=m;i++)
    {
        cin >> v[i];
        upd (i, v[i]);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type==1)
        {
            int poz, val;
            cin >> poz >> val;
            upd (poz, val);
        }
        else
        {
            int st, dr, nod;
            cin >> st >> dr >> nod;
            solve (st, dr, nod);
        }
    }
    return 0;
}

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