Submission #461329

#	Time	Username	Problem	Language	Result	Execution time	Memory
461329		Lawliet	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4011 ms	36864 KiB

treearray

#include <bits/stdc++.h>
 
using namespace std;
 
const int LOG = 20;
const int MAXN = 200010;
 
int LCA(int U, int V);

class LCAStack
{
    public:

        void push(int node)
        {
            nodes.push_back( node );
            prefixLCA.push_back( LCA( node , prefixLCA.back() ) );
        }

        void pop()
        {
            nodes.pop_back();
            prefixLCA.pop_back();
        }

        int topNode() { return nodes.back(); }
        int topLCA() { return prefixLCA.back(); }

        bool empty() { return (int)nodes.size() == 1; }

        LCAStack()
        {
            nodes.push_back( 0 );
            prefixLCA.push_back( 0 );
        }

    protected:

        vector<int> nodes;
        vector<int> prefixLCA;
};

class LCAQueue
{
    public:

        void push(int node) { right.push( node ); }

        void pop()
        {
            if( left.empty() )
            {
                while( !right.empty() )
                {
                    left.push( right.topNode() );
                    right.pop();
                }
            }

            left.pop();
        }

        int getLCA() { return LCA( left.topLCA() , right.topLCA() ); }

    protected:

        LCAStack left, right;
};

int n, m, q;
 
int v[MAXN];
int depth[MAXN];
int tab[LOG][MAXN];
 
vector<int> adj[MAXN];
 
void DFS(int node, int p, int d)
{
    depth[node] = d;
    tab[0][node] = p;
 
    for(int k = 1 ; k < LOG ; k++)
        tab[k][node] = tab[k - 1][tab[k - 1][node]];
 
    for(int i = 0 ; i < (int)adj[node].size() ; i++)
    {
        int viz = adj[node][i];
 
        if( viz != p )
            DFS( viz , node , d + 1 );
    }
}
 
int LCA(int U, int V)
{
    if( U == 0 || V == 0 )
        return max( U , V );

    if( depth[U] < depth[V] )
        swap( U , V );
 
    int d = depth[U] - depth[V];
 
    for(int k = 0 ; k < LOG ; k++)
        if( d & (1 << k) ) U = tab[k][U];
 
    if( U == V ) return U;
 
    for(int k = LOG - 1 ; k >= 0 ; k--)
        if( tab[k][U] != tab[k][V] ) U = tab[k][U], V = tab[k][V];
 
    return tab[0][U];
}
 
void update(int pos, int node) { v[pos] = node; }
 
void query(int l, int r, int node, int& ansL, int& ansR)
{
    ansL = ansR = -1;
 
    for(int i = l ; i <= r ; i++)
    {
        if( v[i] == node )
        {
            ansL = ansR = i;
            return;
        }
    }

    LCAQueue q;

    int i = l, j = l - 1;

    while( j <= r )
    {
        int L = q.getLCA();

        if( L == node )
        {
            ansL = i, ansR = j;
            return;
        }

        if( depth[L] >= depth[node] ) q.push( v[++j] );
        else q.pop(), i++;
    }
}
 
int main()
{
    scanf("%d %d %d",&n,&m,&q);

    depth[0] = n + 1;
 
    for(int i = 1 ; i < n ; i++)
    {
        int U, V;
        scanf("%d %d",&U,&V);
 
        adj[U].push_back( V );
        adj[V].push_back( U );
    }
 
    DFS( 1 , 1 , 0 );
 
    for(int i = 1 ; i <= m ; i++)
        scanf("%d",&v[i]);
 
    for(int i = 1 ; i <= q ; i++)
    {
        int type;
        scanf("%d",&type);
 
        if( type == 1 )
        {
            int pos, node;
            scanf("%d %d",&pos,&node);
 
            update( pos , node );
        }
        if( type == 2 )
        {
            int l, r, node;
            scanf("%d %d %d",&l,&r,&node);
 
            int ansL, ansR;
            query( l , r , node , ansL , ansR );
 
            printf("%d %d\n",ansL,ansR);
        }
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf("%d %d",&U,&V);
      |         ~~~~~^~~~~~~~~~~~~~~
treearray.cpp:168:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:178:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |             scanf("%d %d",&pos,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:185:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |             scanf("%d %d %d",&l,&r,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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