Submission #554914

#	Time	Username	Problem	Language	Result	Execution time	Memory
554914		shahriarkhan	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1030 ms	89612 KiB

treearray

#include<bits/stdc++.h>
using namespace std ;

const int MX = 2e5 + 5 , LG = 25 ;

int up[MX][LG] , tin[MX] , tout[MX] , timer ;

vector<int> adj[MX] ;

set<int> S[MX] , V[MX] ;

void dfs(int s , int p)
{
    tin[s] = ++timer ;
    up[s][0] = p ;
    for(int i = 1 ; i < LG ; ++i)
    {
        up[s][i] = up[up[s][i-1]][i-1] ;
    }
    for(int t : adj[s])
    {
        if(t==p) continue ;
        dfs(t,s) ;
    }
    tout[s] = ++timer ;
}

int is_ancestor(int u , int v)
{
    return ((tin[u]<=tin[v]) && (tout[u]>=tout[v])) ;
}

int find_lca(int u , int v)
{
    if(is_ancestor(u,v)) return u ;
    if(is_ancestor(v,u)) return v ;
    for(int i = LG - 1 ; i >= 0 ; --i)
    {
        if(!is_ancestor(up[u][i],v))
        {
            u = up[u][i] ;
        }
    }
    return up[u][0] ;
}

int main()
{
    int n , m , q ;
    scanf("%d%d%d",&n,&m,&q) ;
    for(int i = 1 ; i < n ; ++i)
    {
        int a , b ;
        scanf("%d%d",&a,&b) ;
        adj[a].push_back(b) ;
        adj[b].push_back(a) ;
    }
    int a[m+2] , b[m+2] ;
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d",&a[i]) ;
        V[a[i]].insert(i) ;
    }
    dfs(1,1) ;
    for(int i = 1 ; i < m ; ++i)
    {
        b[i] = find_lca(a[i],a[i+1]) ;
        S[b[i]].insert(i) ;
    }
    while(q--)
    {
        int type ;
        scanf("%d",&type) ;
        if(type==1)
        {
            int pos , v ;
            scanf("%d%d",&pos,&v) ;
            V[a[pos]].erase(pos) ;
            a[pos] = v ;
            V[a[pos]].insert(pos) ;
            if(pos!=m)
            {
                S[b[pos]].erase(pos) ;
                b[pos] = find_lca(a[pos],a[pos+1]) ;
                S[b[pos]].insert(pos) ;
            }
            if(pos!=1)
            {
                S[b[pos-1]].erase(pos-1) ;
                b[pos-1] = find_lca(a[pos-1],a[pos]) ;
                S[b[pos-1]].insert(pos-1) ;
            }
        }
        else
        {
            int l , r , v ;
            scanf("%d%d%d",&l,&r,&v) ;
            int L = -1 , R = -1 ;
            if(!S[v].empty())
            {
                auto it = S[v].lower_bound(l) ;
                if(it!=S[v].end())
                {
                    int cr = *it ;
                    if(cr<r) L = cr , R = cr + 1 ;
                }
            }
            if(!V[v].empty())
            {
                auto it = V[v].lower_bound(l) ;
                if(it!=V[v].end())
                {
                    int cr = *it ;
                    if(cr<=r) L = cr , R = cr ;
                }
            }
            printf("%d %d\n",L,R) ;
        }
    }
    return 0 ;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d%d",&n,&m,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d",&a,&b) ;
      |         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d",&type) ;
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%d%d",&pos,&v) ;
      |             ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d%d%d",&l,&r,&v) ;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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