oj.uz

Submission #405200

# Submission time Handle Problem Language Result Execution time Memory
405200 2021-05-15T21:27:28 Z CaroLinda Inside information (BOI21_servers) C++14
50 / 100
 375 ms 34212 KB 
#include <bits/stdc++.h>

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] , 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", &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) ;

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

	for(int i = 1 ; i < N+K ; i++ )
	{
		if(queries[i].second == 0) continue ;
		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

servers.cpp: In function 'int main()':
servers.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  scanf("%d %d", &N, &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
servers.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf(" %c", &c ) ;
      |   ~~~~~^~~~~~~~~~~~
servers.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d", &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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7236 KB Output is correct
2 Correct 50 ms 9000 KB Output is correct
3 Correct 71 ms 9120 KB Output is correct
4 Correct 62 ms 9292 KB Output is correct
5 Correct 70 ms 9356 KB Output is correct
6 Correct 79 ms 9060 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7236 KB Output is correct
2 Correct 50 ms 9000 KB Output is correct
3 Correct 71 ms 9120 KB Output is correct
4 Correct 62 ms 9292 KB Output is correct
5 Correct 70 ms 9356 KB Output is correct
6 Correct 79 ms 9060 KB Output is correct
7 Incorrect 43 ms 7364 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7424 KB Output is correct
2 Correct 193 ms 20024 KB Output is correct
3 Correct 204 ms 20040 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7424 KB Output is correct
2 Correct 193 ms 20024 KB Output is correct
3 Correct 204 ms 20040 KB Output is correct
4 Incorrect 47 ms 7392 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7256 KB Output is correct
2 Correct 305 ms 34148 KB Output is correct
3 Correct 327 ms 34120 KB Output is correct
4 Correct 222 ms 34064 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7256 KB Output is correct
2 Correct 305 ms 34148 KB Output is correct
3 Correct 327 ms 34120 KB Output is correct
4 Correct 222 ms 34064 KB Output is correct
5 Incorrect 42 ms 7308 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7264 KB Output is correct
2 Correct 207 ms 22052 KB Output is correct
3 Correct 194 ms 22732 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7264 KB Output is correct
2 Correct 207 ms 22052 KB Output is correct
3 Correct 194 ms 22732 KB Output is correct
4 Incorrect 45 ms 7440 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7236 KB Output is correct
2 Correct 291 ms 34172 KB Output is correct
3 Correct 323 ms 34212 KB Output is correct
4 Correct 207 ms 34028 KB Output is correct
5 Correct 45 ms 8172 KB Output is correct
6 Correct 184 ms 22000 KB Output is correct
7 Correct 182 ms 22556 KB Output is correct
8 Correct 249 ms 25540 KB Output is correct
9 Correct 282 ms 25180 KB Output is correct
10 Correct 356 ms 32260 KB Output is correct
11 Correct 374 ms 31692 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7236 KB Output is correct
2 Correct 291 ms 34172 KB Output is correct
3 Correct 323 ms 34212 KB Output is correct
4 Correct 207 ms 34028 KB Output is correct
5 Correct 45 ms 8172 KB Output is correct
6 Correct 184 ms 22000 KB Output is correct
7 Correct 182 ms 22556 KB Output is correct
8 Correct 249 ms 25540 KB Output is correct
9 Correct 282 ms 25180 KB Output is correct
10 Correct 356 ms 32260 KB Output is correct
11 Correct 374 ms 31692 KB Output is correct
12 Incorrect 51 ms 7368 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7236 KB Output is correct
2 Correct 53 ms 9064 KB Output is correct
3 Correct 73 ms 9048 KB Output is correct
4 Correct 69 ms 9284 KB Output is correct
5 Correct 69 ms 9408 KB Output is correct
6 Correct 75 ms 9028 KB Output is correct
7 Correct 52 ms 8180 KB Output is correct
8 Correct 214 ms 19952 KB Output is correct
9 Correct 191 ms 20052 KB Output is correct
10 Correct 45 ms 8260 KB Output is correct
11 Correct 301 ms 34148 KB Output is correct
12 Correct 291 ms 34152 KB Output is correct
13 Correct 206 ms 34136 KB Output is correct
14 Correct 58 ms 8132 KB Output is correct
15 Correct 167 ms 22080 KB Output is correct
16 Correct 180 ms 22596 KB Output is correct
17 Correct 258 ms 25540 KB Output is correct
18 Correct 246 ms 25028 KB Output is correct
19 Correct 371 ms 32328 KB Output is correct
20 Correct 372 ms 31684 KB Output is correct
21 Correct 223 ms 21004 KB Output is correct
22 Correct 192 ms 21092 KB Output is correct
23 Correct 278 ms 23176 KB Output is correct
24 Correct 262 ms 23808 KB Output is correct
25 Correct 375 ms 29240 KB Output is correct
26 Correct 193 ms 22620 KB Output is correct
27 Correct 172 ms 22256 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7236 KB Output is correct
2 Correct 53 ms 9064 KB Output is correct
3 Correct 73 ms 9048 KB Output is correct
4 Correct 69 ms 9284 KB Output is correct
5 Correct 69 ms 9408 KB Output is correct
6 Correct 75 ms 9028 KB Output is correct
7 Correct 52 ms 8180 KB Output is correct
8 Correct 214 ms 19952 KB Output is correct
9 Correct 191 ms 20052 KB Output is correct
10 Correct 45 ms 8260 KB Output is correct
11 Correct 301 ms 34148 KB Output is correct
12 Correct 291 ms 34152 KB Output is correct
13 Correct 206 ms 34136 KB Output is correct
14 Correct 58 ms 8132 KB Output is correct
15 Correct 167 ms 22080 KB Output is correct
16 Correct 180 ms 22596 KB Output is correct
17 Correct 258 ms 25540 KB Output is correct
18 Correct 246 ms 25028 KB Output is correct
19 Correct 371 ms 32328 KB Output is correct
20 Correct 372 ms 31684 KB Output is correct
21 Correct 223 ms 21004 KB Output is correct
22 Correct 192 ms 21092 KB Output is correct
23 Correct 278 ms 23176 KB Output is correct
24 Correct 262 ms 23808 KB Output is correct
25 Correct 375 ms 29240 KB Output is correct
26 Correct 193 ms 22620 KB Output is correct
27 Correct 172 ms 22256 KB Output is correct
28 Incorrect 43 ms 7388 KB Extra information in the output file
29 Halted 0 ms 0 KB -