oj.uz

Submission #817875

# Submission time Handle Problem Language Result Execution time Memory
817875 2023-08-09T18:30:16 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
70 / 100
 3500 ms 47340 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 3e5 + 10 ;
const int B = 600 ;

int n , q ;

vector< vector< pair<int , int> > >adj(MAX) ;
vector< vector<int> >adj2(MAX) ;

int val[MAX] , up_inc[MAX] , up_dec[MAX] ;
int dep[MAX] , P[MAX][18] ;

int in[MAX] , out[MAX] ;
int tim = 0 ;

vector<int>order ;

void dfs(int node , int par)
{
	in[node] = ++tim , order.push_back(node) ;
	P[node][0] = par ;
	for(int i = 1 ; i < 18 ; ++i)
		P[node][i] = P[P[node][i-1]][i-1] ;
	up_inc[node] = up_dec[node] = par ;
	if(val[node] < val[par])
		up_inc[node] = up_inc[par] ;
	else
		up_dec[node] = up_dec[par] ;
	for(auto &childd : adj[node])
	{
		int child = childd.first , y = childd.second ;
		if(child == par)
			continue ;
		dep[child] = dep[node] + 1 , val[child] = y ;
		dfs(child , node) ;
	}
	out[node] = tim ;
}

bool Ancestor(int x , int y)
{
	return (in[y] >= in[x] && in[y] <= out[x]) ;
}

bool check(int x , int y , int tim) // x has server y
{
	if(x == y)
		return true ;
	if((!Ancestor(up_inc[y] , x)))
		return false ;
	if((!Ancestor(up_dec[x] , y)))
		return false ;
	if(Ancestor(y , x))
		return (val[x] <= tim) ;
	if((!Ancestor(x , y)) && val[x] > tim)
		return false ;
	if(Ancestor(x , y))
	{
		for(int k = 17 ; k >= 0 ; --k)
		{
			if(dep[y] - (1 << k) > dep[x])
				y = P[y][k] ;
		}
		return (val[y] <= tim) ;
	}
	for(int k = 17 ; k >= 0 ; --k)
	{
		if(!Ancestor(P[x][k] , y))
			x = P[x][k] ;
		if(!Ancestor(P[y][k] , x))
			y = P[y][k] ;
	}
	return (val[x] > val[y]) ;
}

int dp[MAX] , dpup[MAX] , dpdown[MAX] ;
int vis[MAX] ;

void dfs2(int node , int par)
{
	vis[node] = 1 ;
	dpdown[node] = dp[node] = 1 ;
	for(auto &child : adj2[node])
	{
		if(child == par)
			continue ;
		dfs2(child , node) ;
		if(val[child] > val[node])
			dpdown[node] += dpdown[child] ;
		dp[node] += dpdown[child] ;
	}
}

void dfs3(int node , int par , int sum)
{
	dpup[node] = sum + (par != node) ;
	if(val[par] > val[node])
		dpup[node] += dpup[par] ;
	dp[node] += dpup[node] ;
	int sz = adj2[node].size() , sum2 = 0 ;
	for(int i = sz-1 ; i >= 0 ; --i)
	{
		int child = adj2[node][i] ;
		if(child == par)
			continue ;
		dfs3(child , node , sum2) ;
		sum2 += dpdown[child] ;
	}
}

void calc()
{
	for(int i = 1 ; i <= n ; ++i)
		vis[i] = 0 ;
	for(auto &node : order)
	{
		if(vis[node])
			continue ;
		dfs2(node , node) ;
		dfs3(node , node , 0) ;
	}
}

char ch[MAX] ;
int X[MAX] , Y[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n+q-1 ; ++i)
	{
		cin>>ch[i] ;
		if(ch[i] == 'S')
		{
			cin>>X[i]>>Y[i] ;
			adj[X[i]].emplace_back(Y[i] , i) ;
			adj[Y[i]].emplace_back(X[i] , i) ;
		}
		else if(ch[i] == 'Q')
			cin>>X[i]>>Y[i] ;
		else if(ch[i] == 'C')
			cin>>X[i] ;
	}
	dfs(1 , 1) ;
	for(int i = 1 ; i <= n ; ++i)
		dp[i] = 1 ;
	int cnt = 0 ;
	vector<int>v ;
	for(int i = 1 ; i <= n+q-1 ; ++i)
	{
		if(cnt == B)
			calc() , cnt = 0 , v.clear() ;
		if(ch[i] == 'S')
		{
			v.push_back(i) ;
			adj2[X[i]].push_back(Y[i]) ;
			adj2[Y[i]].push_back(X[i]) ;
			cnt++ ;
		}
		else if(ch[i] == 'Q')
		{
			if(check(X[i] , Y[i] , i))
				cout<<"yes\n" ;
			else
				cout<<"no\n" ;
		}
		else if(ch[i] == 'C')
		{
			int ans = dp[X[i]] ;
			for(auto &j : v)
			{
				int a = X[j] , b = Y[j] ;
				if(val[a] != j)
					swap(a , b) ;
				if(check(a , X[i] , i) && (!Ancestor(a , X[i])))
					ans++ ;
				else if(check(b , X[i] , i) && Ancestor(a , X[i]))
					ans++ ;
			}
			cout<<ans<<"\n" ;
		}
	}
	return 0 ;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15828 KB Output is correct
2 Correct 26 ms 16608 KB Output is correct
3 Correct 32 ms 16724 KB Output is correct
4 Correct 34 ms 16752 KB Output is correct
5 Correct 25 ms 16788 KB Output is correct
6 Correct 30 ms 16724 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15828 KB Output is correct
2 Correct 26 ms 16608 KB Output is correct
3 Correct 32 ms 16724 KB Output is correct
4 Correct 34 ms 16752 KB Output is correct
5 Correct 25 ms 16788 KB Output is correct
6 Correct 30 ms 16724 KB Output is correct
7 Correct 30 ms 15840 KB Output is correct
8 Correct 182 ms 16500 KB Output is correct
9 Correct 454 ms 16772 KB Output is correct
10 Correct 201 ms 16588 KB Output is correct
11 Correct 241 ms 16812 KB Output is correct
12 Correct 1130 ms 16824 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15836 KB Output is correct
2 Correct 684 ms 39556 KB Output is correct
3 Correct 691 ms 39444 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15836 KB Output is correct
2 Correct 684 ms 39556 KB Output is correct
3 Correct 691 ms 39444 KB Output is correct
4 Correct 48 ms 15836 KB Output is correct
5 Correct 1229 ms 39520 KB Output is correct
6 Correct 1014 ms 39852 KB Output is correct
7 Correct 2101 ms 39592 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15824 KB Output is correct
2 Correct 675 ms 45644 KB Output is correct
3 Correct 672 ms 45644 KB Output is correct
4 Correct 583 ms 47252 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15824 KB Output is correct
2 Correct 675 ms 45644 KB Output is correct
3 Correct 672 ms 45644 KB Output is correct
4 Correct 583 ms 47252 KB Output is correct
5 Correct 28 ms 15828 KB Output is correct
6 Correct 1002 ms 45484 KB Output is correct
7 Correct 1386 ms 46192 KB Output is correct
8 Correct 1055 ms 45388 KB Output is correct
9 Correct 1107 ms 45368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15884 KB Output is correct
2 Correct 406 ms 39064 KB Output is correct
3 Correct 761 ms 39140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15884 KB Output is correct
2 Correct 406 ms 39064 KB Output is correct
3 Correct 761 ms 39140 KB Output is correct
4 Correct 28 ms 15892 KB Output is correct
5 Correct 1004 ms 39008 KB Output is correct
6 Correct 989 ms 38968 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 652 ms 45672 KB Output is correct
3 Correct 669 ms 45576 KB Output is correct
4 Correct 506 ms 47316 KB Output is correct
5 Correct 21 ms 15828 KB Output is correct
6 Correct 364 ms 39000 KB Output is correct
7 Correct 718 ms 39144 KB Output is correct
8 Correct 1010 ms 40300 KB Output is correct
9 Correct 921 ms 40336 KB Output is correct
10 Correct 1979 ms 41860 KB Output is correct
11 Correct 1512 ms 41664 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 652 ms 45672 KB Output is correct
3 Correct 669 ms 45576 KB Output is correct
4 Correct 506 ms 47316 KB Output is correct
5 Correct 21 ms 15828 KB Output is correct
6 Correct 364 ms 39000 KB Output is correct
7 Correct 718 ms 39144 KB Output is correct
8 Correct 1010 ms 40300 KB Output is correct
9 Correct 921 ms 40336 KB Output is correct
10 Correct 1979 ms 41860 KB Output is correct
11 Correct 1512 ms 41664 KB Output is correct
12 Correct 24 ms 15828 KB Output is correct
13 Correct 879 ms 45592 KB Output is correct
14 Correct 1400 ms 46128 KB Output is correct
15 Correct 1070 ms 45412 KB Output is correct
16 Correct 1057 ms 45368 KB Output is correct
17 Correct 27 ms 15828 KB Output is correct
18 Correct 997 ms 39068 KB Output is correct
19 Correct 924 ms 39032 KB Output is correct
20 Correct 1258 ms 40312 KB Output is correct
21 Correct 1124 ms 40248 KB Output is correct
22 Execution timed out 3588 ms 40988 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15908 KB Output is correct
2 Correct 27 ms 16580 KB Output is correct
3 Correct 30 ms 16808 KB Output is correct
4 Correct 29 ms 16708 KB Output is correct
5 Correct 27 ms 16884 KB Output is correct
6 Correct 37 ms 16692 KB Output is correct
7 Correct 23 ms 15888 KB Output is correct
8 Correct 493 ms 39472 KB Output is correct
9 Correct 552 ms 39456 KB Output is correct
10 Correct 22 ms 15828 KB Output is correct
11 Correct 649 ms 45608 KB Output is correct
12 Correct 698 ms 45652 KB Output is correct
13 Correct 543 ms 47340 KB Output is correct
14 Correct 23 ms 15876 KB Output is correct
15 Correct 392 ms 39028 KB Output is correct
16 Correct 708 ms 39072 KB Output is correct
17 Correct 898 ms 40380 KB Output is correct
18 Correct 956 ms 40364 KB Output is correct
19 Correct 1548 ms 41968 KB Output is correct
20 Correct 1519 ms 41668 KB Output is correct
21 Correct 534 ms 39564 KB Output is correct
22 Correct 573 ms 39668 KB Output is correct
23 Correct 755 ms 40320 KB Output is correct
24 Correct 647 ms 40192 KB Output is correct
25 Correct 912 ms 40968 KB Output is correct
26 Correct 949 ms 39020 KB Output is correct
27 Correct 959 ms 39052 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15908 KB Output is correct
2 Correct 27 ms 16580 KB Output is correct
3 Correct 30 ms 16808 KB Output is correct
4 Correct 29 ms 16708 KB Output is correct
5 Correct 27 ms 16884 KB Output is correct
6 Correct 37 ms 16692 KB Output is correct
7 Correct 23 ms 15888 KB Output is correct
8 Correct 493 ms 39472 KB Output is correct
9 Correct 552 ms 39456 KB Output is correct
10 Correct 22 ms 15828 KB Output is correct
11 Correct 649 ms 45608 KB Output is correct
12 Correct 698 ms 45652 KB Output is correct
13 Correct 543 ms 47340 KB Output is correct
14 Correct 23 ms 15876 KB Output is correct
15 Correct 392 ms 39028 KB Output is correct
16 Correct 708 ms 39072 KB Output is correct
17 Correct 898 ms 40380 KB Output is correct
18 Correct 956 ms 40364 KB Output is correct
19 Correct 1548 ms 41968 KB Output is correct
20 Correct 1519 ms 41668 KB Output is correct
21 Correct 534 ms 39564 KB Output is correct
22 Correct 573 ms 39668 KB Output is correct
23 Correct 755 ms 40320 KB Output is correct
24 Correct 647 ms 40192 KB Output is correct
25 Correct 912 ms 40968 KB Output is correct
26 Correct 949 ms 39020 KB Output is correct
27 Correct 959 ms 39052 KB Output is correct
28 Correct 30 ms 15828 KB Output is correct
29 Correct 183 ms 16592 KB Output is correct
30 Correct 470 ms 16788 KB Output is correct
31 Correct 197 ms 16644 KB Output is correct
32 Correct 272 ms 16812 KB Output is correct
33 Correct 1043 ms 16732 KB Output is correct
34 Correct 39 ms 15868 KB Output is correct
35 Correct 988 ms 39564 KB Output is correct
36 Correct 758 ms 39752 KB Output is correct
37 Correct 1837 ms 39696 KB Output is correct
38 Correct 24 ms 15828 KB Output is correct
39 Correct 885 ms 45736 KB Output is correct
40 Correct 1379 ms 46128 KB Output is correct
41 Correct 1026 ms 45380 KB Output is correct
42 Correct 1063 ms 45376 KB Output is correct
43 Correct 27 ms 15828 KB Output is correct
44 Correct 1016 ms 39052 KB Output is correct
45 Correct 910 ms 39208 KB Output is correct
46 Correct 1388 ms 40276 KB Output is correct
47 Correct 1231 ms 40320 KB Output is correct
48 Execution timed out 3584 ms 41092 KB Time limit exceeded
49 Halted 0 ms 0 KB -