Submission #1283778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283778		Faisal_Saqib	Birthday gift (IZhO18_treearray)	C++20	0 / 100	4094 ms	24120 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+100,lg=18;
vector<int> ma[N];
int a[N],h[N],par[N][lg];
void dfs(int x,int p=0)
{
    par[x][0]=p;
    for(int j=1;j<lg;j++)
    {
        par[x][j]=par[par[x][j-1]][j-1];
    }
    for(auto y:ma[x])
    {
        if(y!=p){h[y]=h[x]+1;dfs(y,x);}
    }
}
int lca(int x,int y)
{
    if(x==0)return y;
    if(h[x]<h[y])swap(x,y);
    for(int j=lg-1;j>=0;j--)
    {
        if(h[par[x][j]]>=h[y])
        {
            x=par[x][j];
        }
    }
    if(x==y)return x;
    for(int j=lg-1;j>=0;j--)
    {
        if(par[x][j]!=par[y][j])
        {
            x=par[x][j];
            y=par[y][j];
        }
    }
    return par[x][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    }
    h[1]=1;
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
    }
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int p,v;
            cin>>p>>v;
            a[p]=v;
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            bool tl=0;
            for(int x=l;x<=r and !tl;)
            {
                int lc=a[x];
                int y=x;
                // for(int y=x;y<=r and !tl;y++)
                while(y<=r and h[lca(lc,a[y])]>=h[v])
                {
                    lc=lca(lc,a[y]);
                    if(lc==v)
                    {
                        tl=1;
                        cout<<x<<' '<<y<<endl;
                        break;
                    }
                    y++;
                }
                x=y;
            }
            if(!tl)
                cout<<-1<<' '<<-1<<endl;
        }
    }
}

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