Submission #408727

#	Time	Username	Problem	Language	Result	Execution time	Memory
408727		CaroLinda	Inside information (BOI21_servers)	C++14	100 / 100	1551 ms	59380 KiB

servers

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())

const int MAXN = 240010 ;
const int LOG = 20 ;

using namespace std ;

int N , K ;
int aresta_pai[MAXN] , max_crescente[MAXN] , max_decrescente[MAXN] ;
int lvl[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 ;
}
void dfs(int x)
{

	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) ;

	}

}

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] ;

}

//CENTROID DECOMPOSITION STUFF -------------------

int bit[MAXN*LOG] ;
void upd(int i) { for(; i < MAXN*LOG ; i += i &-i ) bit[i]++ ;  }
int qry(int i )
{
	int tot = 0 ;
	for(; i > 0 ; i -= i &-i ) tot += bit[i] ;
	return tot ;
}

bool marc[MAXN] ;
int qtd ;
int edge[MAXN][LOG] ;
int lim_down[MAXN] , lim_up[MAXN] ;
int sub[MAXN] ;
int cn_parent[MAXN] , cn_table[MAXN][LOG] ;
int cn_lvl[MAXN] ;
bool can[MAXN][LOG] ;

void dfs1(int x, int par )
{
	sub[x] = 1 ;
	for(auto e : adj[x])
	{
		if(marc[e.first] || par == e.first ) continue ;
		dfs1(e.first, x) ;
		sub[x]+=sub[e.first] ;
	}
}

int dfs2(int x, int par )
{
	for(auto e : adj[x] ) 
	{
		if(marc[e.first] || par == e.first ) continue ;
		if( sub[e.first] > qtd/2 ) return dfs2(e.first, x) ;
	}
	return x ;
}

void dfs3(int x, int par , int cn , int val )
{
	edge[x][ cn_lvl[cn] ] = val ;
	cn_table[x][ cn_lvl[cn] ] = cn ;

	int k ;
	for(auto e : adj[x] )
		if(e.first == par ) k = e.second ;

	for(auto e : adj[x] )
	{
		if( marc[e.first] || e.first == par ) continue ;

		can[e.first][ cn_lvl[ cn ] ] = ( e.second > k )&can[x][ cn_lvl[cn] ] ;
		dfs3(e.first, x, cn , val ) ;
	}

}

int currTime ;
void decompose(int x, int centroid_parent )
{
	dfs1(x,-1) ;
	qtd = sub[x] ;

	int cn = dfs2(x,-1) ;

	cn_parent[cn] = centroid_parent ;
	cn_lvl[cn] = cn_lvl[ centroid_parent ]+1 ;

	lim_down[cn] = currTime+1 ;

	for(auto e : adj[cn] ) currTime += !marc[e.first] ;

	lim_up[cn] = currTime ;

	for(int i = 0 , id = lim_down[cn] ; i < sz(adj[cn]) ; i++ , id++ )
	{
		int e = adj[cn][i].first; 

		if(marc[e]) { id-- ; continue ; }

		can[ e ][ cn_lvl[cn] ] = true ;
		dfs3( e , cn , cn , id ) ;

	}

	marc[cn] = true ;

	for(auto e : adj[cn] )
		if( !marc[e.first] ) decompose(e.first, cn ) ;
}

//---------------------------------------------

void makeUpdate(int u, int v)
{

	for(int i = 0 ; i < 2 ; i++ , swap(u,v) ) 
	{

		int k = cn_parent[u] ;

		while( k )
		{
			if( join(u,k, true) && !join(v, k, true) && can[u][ cn_lvl[k] ] )
				upd( edge[u][ cn_lvl[k] ] ) ;
			k = cn_parent[k] ;
		}

	}

	//don't forget to join both of them afterwards
	join(u, v) ;
}

bool arrives(int u, int v)
{
	if( join(u, v, true) ) return false ;

	int k = lca(u,v) ;

	if( lvl[ max_decrescente[u] ] <= lvl[k] && lvl[ max_crescente[v] ] <= lvl[k]  )
	{
		if( k == u || k == v ) return true ;

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

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

		if( aresta_pai[v] < aresta_pai[u] ) return true ;

	}

	return false ;
}

int makeQuery(int u)
{

	int ans = qry( lim_up[u] ) - qry(lim_down[u]-1) + 1 ;
	int k = cn_parent[u] ;

	while( k )
	{

		if( arrives(k, u) )
		{
			int my_code = edge[u][ cn_lvl[k] ] ;
			ans += qry(lim_up[k])-qry(my_code)+1 ;
		}

		k = cn_parent[k] ;
	}

	return ans ;
}

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

		if(c == 'C') continue ;
		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) ;
	decompose(1,0) ;

	/*for(int i = 1 ; i <= N ; i++ ) 
	{
		cout << "About " << i << ": " << endl ;
		cout << cn_parent[i] <<" " << cn_lvl[i] << " " << lim_down[i] <<" " << lim_up[i] << endl ;
		for(int j = 1 ; j <= 3 ; j++ ) cout << can[i][j] << " " << edge[i][j] << endl ;
		cout << endl ;
	} */

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

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

		printf("%s\n" , arrives(queries[i].first, queries[i].second ) ? "yes" : "no") ;

	}
}

Compilation message (stderr)

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

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