Submission #896624

#	Time	Username	Problem	Language	Result	Execution time	Memory
896624		Denkata	Birthday gift (IZhO18_treearray)	C++14	100 / 100	865 ms	102356 KiB

treearray

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 2e5+3;
vector <int> v[maxn];
int tin[maxn],tout[maxn];
vector <int> up[maxn];
int timer,i,j,p,q,n,m,k,l,Q,a[maxn];

void dfs(int u,int p)
{
    int i;
    tin[u]=++timer;
    up[u][0]=p;
    for(i=1;i<=l;i++)
    {
        up[u][i]=up[up[u][i-1]][i-1];
    }
    for(i=0;i<v[u].size();i++)
    {
        int q=v[u][i];
        if(q!=p)
        {
            dfs(q,u);
        }
    }
    tout[u]=++timer;
}
bool upper(int a,int b)
{
    return (tin[a]<=tin[b] && tout[a]>=tout[b]);
}
int lca(int a,int b)
{
    if(upper(a,b))return a;
    if(upper(b,a))return b;
    for(i=l;i>=0;i--)
    {
        if(!upper(up[a][i],b))
            a=up[a][i];
    }
    return up[a][0];
}
set <int> s[maxn],s2[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>Q;
    l=1;
    while((1<<l)<=n)
        l++;
    for(i=1;i<n;i++)
    {
        cin>>p>>q;
        v[p].push_back(q);
        v[q].push_back(p);
    }
    for(i=0;i<=n+1;i++)
        up[i].resize(l+10);
    tout[0]=100000000;
    dfs(1,1);
    for(i=1;i<=m;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        s2[a[i]].insert(i);
        if(i+1<=m)
            s[lca(a[i],a[i+1])].insert(i);
    }
    while(Q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            cin>>p>>q;
            s2[a[p]].erase(p);
            if(p+1<=m)
                s[lca(a[p],a[p+1])].erase(p);
            if(p-1>=1)
                s[lca(a[p-1],a[p])].erase(p-1);


            s2[q].insert(p);
            a[p] = q;
            if(p+1<=m)
                s[lca(a[p],a[p+1])].insert(p);
            if(p-1>=1)
                s[lca(a[p-1],a[p])].insert(p-1);
        }
        else
        {
            int l,r,vv;
            cin>>l>>r>>vv;
            auto it = s2[vv].lower_bound(l);
            if(it!=s2[vv].end() && (*it)<=r)///nqma takuv ili ne vliza v [l;r]
            {
                cout<<*it<<" "<<*it<<endl;
                continue;
            }
            else
            {
                it = s[vv].lower_bound(l);
                if(it!=s[vv].end() && (*it)+1<=r)
                {
                    cout<<*it<<" "<<(*it)+1<<endl;
                    continue;
                }
            }
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(i=0;i<v[u].size();i++)
      |             ~^~~~~~~~~~~~

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