Submission #416596

#	Time	Username	Problem	Language	Result	Execution time	Memory
416596		Lawliet	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1512 ms	87092 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;
const int MAXN = 200010;

int n, m, q;

int v[MAXN];
int depth[MAXN];
int tab[LOG][MAXN];

vector<int> adj[MAXN];

set<int> nodes[MAXN];
set<int> nodePair[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( 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)
{
    nodes[ v[pos] ].erase( pos );
    nodes[ node ].insert( pos );

    if( pos != 1 )
    {
        nodePair[ LCA( v[pos - 1] , v[pos] ) ].erase( pos - 1 );
        nodePair[ LCA( v[pos - 1] , node ) ].insert( pos - 1 );
    }
    if( pos != m )
    {
        nodePair[ LCA( v[pos + 1] , v[pos] ) ].erase( pos );
        nodePair[ LCA( v[pos + 1] , node ) ].insert( pos );
    }

    v[pos] = node;
}

void query(int l, int r, int node, int& ansL, int& ansR)
{
    ansL = ansR = -1;

    auto it = nodes[node].lower_bound(l);

    if( it != nodes[node].end() && *it <= r )
        ansL = ansR = *it;

    it = nodePair[node].lower_bound(l);

    if( it != nodePair[node].end() && *it < r )
        ansL = *it, ansR = *it + 1;
}

int main()
{
    scanf("%d %d %d",&n,&m,&q);

    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]);
        nodes[ v[i] ].insert( i );
    }

    for(int i = 1 ; i < m ; i++)
        nodePair[ LCA( v[i] , v[i + 1] ) ].insert( 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:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d %d",&U,&V);
      |         ~~~~~^~~~~~~~~~~~~~~
treearray.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |             scanf("%d %d",&pos,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |             scanf("%d %d %d",&l,&r,&node);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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