oj.uz

답안 #405178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405178 2021-05-15T20:24:57 Z CaroLinda Inside information (BOI21_servers) C++14
0 / 100
 51 ms 4548 KB 
#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_crescente[queries[i].second] ] <= lvl[k] && lvl[ max_decrescente[queries[i].second] ] <= 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 j = 0 ; j < 2 ; j++ , swap(x,y) )
			{
				for(int g = LOG-1 ; g >= 0 ; g-- )
					if( tab[g][x] && lvl[ tab[g][x] ] > lvl[k] )
						x = tab[g][x] ;
			}

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

		}

		printf("no\n") ;

	}
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 4496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 4496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 4476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 4476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 4532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 4532 KB Output isn't correct
2 Halted 0 ms 0 KB -