Submission #405189

#	Time	Username	Problem	Language	Result	Execution time	Memory
405189		CaroLinda	Inside information (BOI21_servers)	C++14	0 / 100	46 ms	4548 KiB

servers

#include <bits/stdc++.h>

const int MAXN = 120010 ;
const int LOG = 20 ;

using namespace std ;

int N , K ;
int aresta_pai[MAXN] , max_crescente[MAXN] , max_decrescente[MAXN] ;
int last_crescente[MAXN] , last_decrescente[MAXN] ;
int lvl[MAXN] , tin[MAXN] , tout[MAXN] ;
int tab[LOG][MAXN] ;
pair<int,int> queries[MAXN] ;
vector< pair<int,int> > adj[MAXN] ;
int dsu[MAXN] ;

int find(int x) { return dsu[x] = (dsu[x] == x ) ? x : find(dsu[x]) ;  }
bool join(int x, int y, bool consulta = false )
{
	x = find(x) ;
	y = find(y) ;

	if(x == y) return false ;


	if( rand() % 2  ) swap(x,y) ;
	if( !consulta ) dsu[x] = y ;
 
	return true ;
}

int currTime ;
void dfs(int x)
{
	tin[x] = tout[x] = ++currTime ;

	for(int i = 1 ; i< LOG && tab[i-1][x] ; i++ )
		tab[i][x] = tab[i-1][ tab[i-1][x] ] ;

	max_crescente[x] = max_decrescente[x] = tab[0][x] ;
	
	if( tab[0][ tab[0][x] ] && aresta_pai[x] < aresta_pai[tab[0][x]] )
		max_crescente[x] = max_crescente[ tab[0][x] ] ;

	if( tab[0][ tab[0][x] ] && aresta_pai[x] > aresta_pai[tab[0][x]] )
		max_decrescente[x] = max_decrescente[ tab[0][x] ] ;

	for(auto e : adj[x] )
	{
		if(e.first == tab[0][x]) continue ;

		tab[0][e.first] = x ;
		aresta_pai[e.first] = e.second ;
		lvl[e.first] = lvl[x]+1 ;

		dfs(e.first) ;

	}

	tout[x] = currTime ;
}

int lca(int x, int y)
{
	if( lvl[x] < lvl[y] ) swap(x,y) ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( tab[i][x] && lvl[tab[i][x]] >= lvl[y] )
			x = tab[i][x] ;

	if(x==y)return y ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( tab[i][x] && tab[i][x] != tab[i][y] )
		{
			x = tab[i][x] ;
			y= tab[i][y] ;
		}

	return tab[0][x] ;

}

int main()
{
	scanf("%d %d", &N, &K ) ;	
	for(int i = 1 , a ,b  ; i < N+K ; i++ )
	{
		char c ;
		scanf(" %c %d", &c , &queries[i].first ) ;

		if(c == 'C') return 0 ;
		else scanf("%d", &queries[i].second ) ;

		if( c == 'S' )
		{	
			a = queries[i].first ;
			b = queries[i].second ;

			queries[i] = make_pair(-a,-b) ;

			adj[a].push_back( make_pair(b,i) ) ;
			adj[b].push_back( make_pair(a,i) ) ;
		}

	}

	dfs(1) ;

	iota(dsu+1, dsu+1+N , 1 ) ;

	for(int i = 1 ; i < N+K ; i++ )
	{
		if( queries[i].first < 0 ) 
		{
			join(-queries[i].first, -queries[i].second ) ;
			continue ;
		}
		if( join(queries[i].first, queries[i].second, true) ) { printf("no\n") ; continue ; }

		int k = lca(queries[i].first, queries[i].second) ;

		if( lvl[ max_decrescente[queries[i].first] ] <= lvl[k] && lvl[ max_crescente[queries[i].second] ] <= lvl[k]  )
		{
			if( k == queries[i].second || k == queries[i].first ) { printf("yes\n") ; continue ; }

			int x = queries[i].first ;
			int y = queries[i].second ;

			for(int g = LOG-1 ; g >= 0 ; g-- )
				if( tab[g][x] && lvl[ tab[g][x] ] > lvl[k] )
					x = tab[g][x] ;

			for(int g = LOG-1 ; g >= 0 ; g-- )
				if( tab[g][y] && lvl[ tab[g][y] ] > lvl[k] )
					y = tab[g][y] ;

			if( aresta_pai[y] < aresta_pai[x] ) { printf("yes\n" ) ; continue ; }

		}

		printf("no\n") ;

	}
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d %d", &N, &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
servers.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf(" %c %d", &c , &queries[i].first ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:93:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   else scanf("%d", &queries[i].second ) ;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5