Submission #465859

#	Time	Username	Problem	Language	Result	Execution time	Memory
465859		CaroLinda	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4070 ms	79492 KiB

treearray

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int MAXN = 2e5+10 ;
const int LOG = 20 ;

using namespace std ;
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int N , M , Q ;
int arr[MAXN ] ;
int dp[LOG][MAXN] , lvl[MAXN] ;
vector<int> adj[MAXN] ;
ordered_set o_set[MAXN] , norma[MAXN] ;

void dfs(int x)
{
	for(int i = 1 ; dp[i-1][x] != -1 ; i++ )
		dp[i][x] = dp[i-1][ dp[i-1][x] ] ;
		
	for(auto e : adj[x] )
	{
		if(e == dp[0][x]) continue ;
		dp[0][e] = x ;
		lvl[e] = lvl[x]+1 ;
		dfs(e) ;
	}
}

int getLca(int x, int y)
{
	if(lvl[x] < lvl[y])	 swap(x,y) ;
	
	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( dp[i][x] != -1 && lvl[dp[i][x]] >= lvl[y] )
			x = dp[i][x] ;
	
	if(x == y ) return x ;
	
	for(int i  = LOG-1 ; i >= 0 ; i-- )
		if(dp[i][x] != -1 && dp[i][x] != dp[i][y])
		{
			x = dp[i][x] ;
			y = dp[i][y] ;
		}
	
	return dp[0][x] ;
}

void op(int idx, int type )
{
	int L ;
	
	if(type == -1) norma[ arr[idx] ].erase( norma[ arr[idx] ].find(idx) ) ;
	else norma[arr[idx]].insert(idx) ;
	
	if( idx > 1 ) 
	{
		L = getLca(arr[idx-1] , arr[idx]) ;
		
		if(type == -1) o_set[L].erase( o_set[L].find(idx-1) ) ;
		else o_set[L].insert(idx-1) ;
	}
	if(idx+1 <= M)
	{
		L = getLca(arr[idx] , arr[idx+1]) ;
		
		if(type == -1) o_set[L].erase( o_set[L].find(idx) ) ;
		else o_set[L].insert(idx) ;
	}
}

int main()
{
	memset(dp, -1, sizeof dp );
	
	cin >> N >> M >> Q ;
	for(int i = 0 , x , y; i < N-1 ; i++ )
	{
		scanf("%d %d", &x, &y ) ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	
	dfs(1) ;
	
	for(int i = 1 ; i <= M ; i++ ) scanf("%d", &arr[i] ) , norma[arr[i]].insert(i) ;
	for(int i = 1 ; i < M ; i++ ) o_set[ getLca(arr[i] , arr[i+1]) ].insert(i) ;
	
	while(Q--)
	{
		int t , L , R , v , pos ;
		scanf("%d", &t ) ;
		if(t == 1)
		{
			scanf("%d %d", &pos, &v ) ;
			arr[pos] = v ;
		}
		else
		{
			scanf("%d %d %d", &L, &R, &v ) ;
		
			int l = -1 , r = -1 ;
			
			for(int i = L ; i <= R ; i++ ) 
				if(arr[i] == v ) l = r = i ;
			
			for(int i = L ; i < R ; i++ )
			{
				if(getLca(arr[i] , arr[i+1]) == v ) l = i , r = i+1 ;			
			}
				
			printf("%d %d\n" , l , r  ) ;
		}
	}
	
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d %d", &x, &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:91:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  for(int i = 1 ; i <= M ; i++ ) scanf("%d", &arr[i] ) , norma[arr[i]].insert(i) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", &t ) ;
      |   ~~~~~^~~~~~~~~~~
treearray.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d %d", &pos, &v ) ;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d %d %d", &L, &R, &v ) ;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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