oj.uz

Submission #408727

# Submission time Handle Problem Language Result Execution time Memory
408727 2021-05-19T14:52:34 Z CaroLinda Inside information (BOI21_servers) C++14
100 / 100
 1551 ms 59380 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7452 KB Output is correct
2 Correct 61 ms 8636 KB Output is correct
3 Correct 79 ms 8716 KB Output is correct
4 Correct 64 ms 8884 KB Output is correct
5 Correct 83 ms 9068 KB Output is correct
6 Correct 82 ms 8736 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7452 KB Output is correct
2 Correct 61 ms 8636 KB Output is correct
3 Correct 79 ms 8716 KB Output is correct
4 Correct 64 ms 8884 KB Output is correct
5 Correct 83 ms 9068 KB Output is correct
6 Correct 82 ms 8736 KB Output is correct
7 Correct 51 ms 7536 KB Output is correct
8 Correct 87 ms 8608 KB Output is correct
9 Correct 81 ms 8780 KB Output is correct
10 Correct 94 ms 8860 KB Output is correct
11 Correct 158 ms 8956 KB Output is correct
12 Correct 70 ms 8648 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7380 KB Output is correct
2 Correct 293 ms 40424 KB Output is correct
3 Correct 273 ms 40384 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7380 KB Output is correct
2 Correct 293 ms 40424 KB Output is correct
3 Correct 273 ms 40384 KB Output is correct
4 Correct 56 ms 7388 KB Output is correct
5 Correct 264 ms 40440 KB Output is correct
6 Correct 169 ms 40724 KB Output is correct
7 Correct 224 ms 40504 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7444 KB Output is correct
2 Correct 870 ms 56120 KB Output is correct
3 Correct 812 ms 56040 KB Output is correct
4 Correct 548 ms 55916 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7444 KB Output is correct
2 Correct 870 ms 56120 KB Output is correct
3 Correct 812 ms 56040 KB Output is correct
4 Correct 548 ms 55916 KB Output is correct
5 Correct 55 ms 7376 KB Output is correct
6 Correct 771 ms 55748 KB Output is correct
7 Correct 740 ms 56032 KB Output is correct
8 Correct 786 ms 55808 KB Output is correct
9 Correct 778 ms 55820 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7416 KB Output is correct
2 Correct 418 ms 45276 KB Output is correct
3 Correct 548 ms 45752 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7416 KB Output is correct
2 Correct 418 ms 45276 KB Output is correct
3 Correct 548 ms 45752 KB Output is correct
4 Correct 53 ms 7544 KB Output is correct
5 Correct 479 ms 44920 KB Output is correct
6 Correct 587 ms 45364 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7364 KB Output is correct
2 Correct 751 ms 55916 KB Output is correct
3 Correct 748 ms 55912 KB Output is correct
4 Correct 521 ms 56008 KB Output is correct
5 Correct 50 ms 7364 KB Output is correct
6 Correct 418 ms 45244 KB Output is correct
7 Correct 557 ms 45892 KB Output is correct
8 Correct 625 ms 48904 KB Output is correct
9 Correct 670 ms 48448 KB Output is correct
10 Correct 819 ms 56596 KB Output is correct
11 Correct 826 ms 55600 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7364 KB Output is correct
2 Correct 751 ms 55916 KB Output is correct
3 Correct 748 ms 55912 KB Output is correct
4 Correct 521 ms 56008 KB Output is correct
5 Correct 50 ms 7364 KB Output is correct
6 Correct 418 ms 45244 KB Output is correct
7 Correct 557 ms 45892 KB Output is correct
8 Correct 625 ms 48904 KB Output is correct
9 Correct 670 ms 48448 KB Output is correct
10 Correct 819 ms 56596 KB Output is correct
11 Correct 826 ms 55600 KB Output is correct
12 Correct 51 ms 7504 KB Output is correct
13 Correct 773 ms 58968 KB Output is correct
14 Correct 704 ms 59092 KB Output is correct
15 Correct 775 ms 58444 KB Output is correct
16 Correct 757 ms 58564 KB Output is correct
17 Correct 63 ms 8272 KB Output is correct
18 Correct 487 ms 44972 KB Output is correct
19 Correct 593 ms 45432 KB Output is correct
20 Correct 799 ms 47952 KB Output is correct
21 Correct 707 ms 48384 KB Output is correct
22 Correct 1127 ms 55016 KB Output is correct
23 Correct 1536 ms 54612 KB Output is correct
24 Correct 1008 ms 54564 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7404 KB Output is correct
2 Correct 63 ms 8676 KB Output is correct
3 Correct 79 ms 8676 KB Output is correct
4 Correct 62 ms 8900 KB Output is correct
5 Correct 80 ms 9076 KB Output is correct
6 Correct 81 ms 8644 KB Output is correct
7 Correct 54 ms 7480 KB Output is correct
8 Correct 281 ms 43276 KB Output is correct
9 Correct 263 ms 43228 KB Output is correct
10 Correct 50 ms 8284 KB Output is correct
11 Correct 754 ms 59204 KB Output is correct
12 Correct 773 ms 59284 KB Output is correct
13 Correct 511 ms 59380 KB Output is correct
14 Correct 51 ms 8220 KB Output is correct
15 Correct 412 ms 45432 KB Output is correct
16 Correct 528 ms 45880 KB Output is correct
17 Correct 604 ms 48932 KB Output is correct
18 Correct 648 ms 48456 KB Output is correct
19 Correct 810 ms 56448 KB Output is correct
20 Correct 805 ms 55624 KB Output is correct
21 Correct 282 ms 44292 KB Output is correct
22 Correct 292 ms 44332 KB Output is correct
23 Correct 475 ms 46416 KB Output is correct
24 Correct 484 ms 47060 KB Output is correct
25 Correct 776 ms 56152 KB Output is correct
26 Correct 515 ms 45872 KB Output is correct
27 Correct 480 ms 45540 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7404 KB Output is correct
2 Correct 63 ms 8676 KB Output is correct
3 Correct 79 ms 8676 KB Output is correct
4 Correct 62 ms 8900 KB Output is correct
5 Correct 80 ms 9076 KB Output is correct
6 Correct 81 ms 8644 KB Output is correct
7 Correct 54 ms 7480 KB Output is correct
8 Correct 281 ms 43276 KB Output is correct
9 Correct 263 ms 43228 KB Output is correct
10 Correct 50 ms 8284 KB Output is correct
11 Correct 754 ms 59204 KB Output is correct
12 Correct 773 ms 59284 KB Output is correct
13 Correct 511 ms 59380 KB Output is correct
14 Correct 51 ms 8220 KB Output is correct
15 Correct 412 ms 45432 KB Output is correct
16 Correct 528 ms 45880 KB Output is correct
17 Correct 604 ms 48932 KB Output is correct
18 Correct 648 ms 48456 KB Output is correct
19 Correct 810 ms 56448 KB Output is correct
20 Correct 805 ms 55624 KB Output is correct
21 Correct 282 ms 44292 KB Output is correct
22 Correct 292 ms 44332 KB Output is correct
23 Correct 475 ms 46416 KB Output is correct
24 Correct 484 ms 47060 KB Output is correct
25 Correct 776 ms 56152 KB Output is correct
26 Correct 515 ms 45872 KB Output is correct
27 Correct 480 ms 45540 KB Output is correct
28 Correct 52 ms 7548 KB Output is correct
29 Correct 80 ms 9668 KB Output is correct
30 Correct 80 ms 9660 KB Output is correct
31 Correct 95 ms 9756 KB Output is correct
32 Correct 155 ms 9948 KB Output is correct
33 Correct 74 ms 9668 KB Output is correct
34 Correct 55 ms 8260 KB Output is correct
35 Correct 271 ms 43188 KB Output is correct
36 Correct 166 ms 42296 KB Output is correct
37 Correct 181 ms 42464 KB Output is correct
38 Correct 65 ms 8244 KB Output is correct
39 Correct 795 ms 58812 KB Output is correct
40 Correct 718 ms 59040 KB Output is correct
41 Correct 787 ms 58472 KB Output is correct
42 Correct 787 ms 58464 KB Output is correct
43 Correct 56 ms 8260 KB Output is correct
44 Correct 507 ms 44924 KB Output is correct
45 Correct 617 ms 45520 KB Output is correct
46 Correct 833 ms 47952 KB Output is correct
47 Correct 691 ms 48216 KB Output is correct
48 Correct 1110 ms 54936 KB Output is correct
49 Correct 1551 ms 54628 KB Output is correct
50 Correct 1018 ms 54652 KB Output is correct
51 Correct 211 ms 43968 KB Output is correct
52 Correct 196 ms 43972 KB Output is correct
53 Correct 181 ms 43436 KB Output is correct
54 Correct 175 ms 43980 KB Output is correct
55 Correct 214 ms 43928 KB Output is correct
56 Correct 483 ms 46240 KB Output is correct
57 Correct 645 ms 55032 KB Output is correct
58 Correct 760 ms 45384 KB Output is correct
59 Correct 526 ms 46092 KB Output is correct