oj.uz

Submission #817885

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

using namespace std ;

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

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 ;
	bool flag = false ;
	if(dep[x] < dep[y])
		swap(x , y) , flag = true ;
	for(int k = 17 ; k >= 0 ; --k)
	{
		if(dep[x] - (1 << k) > dep[y])
			x = P[x][k] ;
	}
	if(P[x][0] == y)
		return (val[x] <= tim) ;
	if(dep[x] != dep[y])
		x = P[x][0] ;
	if(flag)
		swap(x , y) ;
	for(int k = 17 ; k >= 0 ; --k)
	{
		if(P[x][k] != P[y][k])
			x = P[x][k] , 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 22 ms 15840 KB Output is correct
2 Correct 28 ms 16584 KB Output is correct
3 Correct 29 ms 16804 KB Output is correct
4 Correct 28 ms 16636 KB Output is correct
5 Correct 32 ms 16880 KB Output is correct
6 Correct 31 ms 16656 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15840 KB Output is correct
2 Correct 28 ms 16584 KB Output is correct
3 Correct 29 ms 16804 KB Output is correct
4 Correct 28 ms 16636 KB Output is correct
5 Correct 32 ms 16880 KB Output is correct
6 Correct 31 ms 16656 KB Output is correct
7 Correct 29 ms 15840 KB Output is correct
8 Correct 147 ms 16516 KB Output is correct
9 Correct 365 ms 16920 KB Output is correct
10 Correct 165 ms 16608 KB Output is correct
11 Correct 256 ms 16816 KB Output is correct
12 Correct 1020 ms 16908 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15872 KB Output is correct
2 Correct 647 ms 39576 KB Output is correct
3 Correct 689 ms 39484 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15872 KB Output is correct
2 Correct 647 ms 39576 KB Output is correct
3 Correct 689 ms 39484 KB Output is correct
4 Correct 40 ms 15828 KB Output is correct
5 Correct 1039 ms 39472 KB Output is correct
6 Correct 834 ms 39820 KB Output is correct
7 Correct 1693 ms 39648 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15892 KB Output is correct
2 Correct 865 ms 45680 KB Output is correct
3 Correct 867 ms 45664 KB Output is correct
4 Correct 649 ms 47340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15892 KB Output is correct
2 Correct 865 ms 45680 KB Output is correct
3 Correct 867 ms 45664 KB Output is correct
4 Correct 649 ms 47340 KB Output is correct
5 Correct 27 ms 15820 KB Output is correct
6 Correct 1045 ms 45468 KB Output is correct
7 Correct 1405 ms 46176 KB Output is correct
8 Correct 1125 ms 45460 KB Output is correct
9 Correct 1088 ms 45412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15888 KB Output is correct
2 Correct 470 ms 39008 KB Output is correct
3 Correct 1037 ms 39124 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15888 KB Output is correct
2 Correct 470 ms 39008 KB Output is correct
3 Correct 1037 ms 39124 KB Output is correct
4 Correct 28 ms 15896 KB Output is correct
5 Correct 809 ms 39068 KB Output is correct
6 Correct 1102 ms 39032 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15912 KB Output is correct
2 Correct 884 ms 45600 KB Output is correct
3 Correct 883 ms 45684 KB Output is correct
4 Correct 680 ms 47368 KB Output is correct
5 Correct 22 ms 15856 KB Output is correct
6 Correct 475 ms 38948 KB Output is correct
7 Correct 899 ms 39168 KB Output is correct
8 Correct 1198 ms 40260 KB Output is correct
9 Correct 1155 ms 40400 KB Output is correct
10 Correct 2193 ms 41800 KB Output is correct
11 Correct 2127 ms 41664 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15912 KB Output is correct
2 Correct 884 ms 45600 KB Output is correct
3 Correct 883 ms 45684 KB Output is correct
4 Correct 680 ms 47368 KB Output is correct
5 Correct 22 ms 15856 KB Output is correct
6 Correct 475 ms 38948 KB Output is correct
7 Correct 899 ms 39168 KB Output is correct
8 Correct 1198 ms 40260 KB Output is correct
9 Correct 1155 ms 40400 KB Output is correct
10 Correct 2193 ms 41800 KB Output is correct
11 Correct 2127 ms 41664 KB Output is correct
12 Correct 25 ms 15828 KB Output is correct
13 Correct 991 ms 45604 KB Output is correct
14 Correct 1348 ms 46100 KB Output is correct
15 Correct 1115 ms 45464 KB Output is correct
16 Correct 1126 ms 45416 KB Output is correct
17 Correct 27 ms 15828 KB Output is correct
18 Correct 849 ms 39056 KB Output is correct
19 Correct 1140 ms 39012 KB Output is correct
20 Correct 1459 ms 40316 KB Output is correct
21 Correct 1444 ms 40252 KB Output is correct
22 Execution timed out 3534 ms 41092 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15868 KB Output is correct
2 Correct 26 ms 16596 KB Output is correct
3 Correct 30 ms 16712 KB Output is correct
4 Correct 28 ms 16724 KB Output is correct
5 Correct 35 ms 16780 KB Output is correct
6 Correct 32 ms 16716 KB Output is correct
7 Correct 24 ms 15840 KB Output is correct
8 Correct 701 ms 39452 KB Output is correct
9 Correct 699 ms 39508 KB Output is correct
10 Correct 21 ms 15872 KB Output is correct
11 Correct 843 ms 45628 KB Output is correct
12 Correct 962 ms 45608 KB Output is correct
13 Correct 700 ms 47304 KB Output is correct
14 Correct 21 ms 15824 KB Output is correct
15 Correct 515 ms 38988 KB Output is correct
16 Correct 984 ms 39068 KB Output is correct
17 Correct 1216 ms 40384 KB Output is correct
18 Correct 1265 ms 40428 KB Output is correct
19 Correct 1851 ms 41828 KB Output is correct
20 Correct 1826 ms 41636 KB Output is correct
21 Correct 812 ms 39516 KB Output is correct
22 Correct 702 ms 39512 KB Output is correct
23 Correct 860 ms 40252 KB Output is correct
24 Correct 884 ms 40200 KB Output is correct
25 Correct 1262 ms 40944 KB Output is correct
26 Correct 1237 ms 39056 KB Output is correct
27 Correct 1227 ms 39044 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15868 KB Output is correct
2 Correct 26 ms 16596 KB Output is correct
3 Correct 30 ms 16712 KB Output is correct
4 Correct 28 ms 16724 KB Output is correct
5 Correct 35 ms 16780 KB Output is correct
6 Correct 32 ms 16716 KB Output is correct
7 Correct 24 ms 15840 KB Output is correct
8 Correct 701 ms 39452 KB Output is correct
9 Correct 699 ms 39508 KB Output is correct
10 Correct 21 ms 15872 KB Output is correct
11 Correct 843 ms 45628 KB Output is correct
12 Correct 962 ms 45608 KB Output is correct
13 Correct 700 ms 47304 KB Output is correct
14 Correct 21 ms 15824 KB Output is correct
15 Correct 515 ms 38988 KB Output is correct
16 Correct 984 ms 39068 KB Output is correct
17 Correct 1216 ms 40384 KB Output is correct
18 Correct 1265 ms 40428 KB Output is correct
19 Correct 1851 ms 41828 KB Output is correct
20 Correct 1826 ms 41636 KB Output is correct
21 Correct 812 ms 39516 KB Output is correct
22 Correct 702 ms 39512 KB Output is correct
23 Correct 860 ms 40252 KB Output is correct
24 Correct 884 ms 40200 KB Output is correct
25 Correct 1262 ms 40944 KB Output is correct
26 Correct 1237 ms 39056 KB Output is correct
27 Correct 1227 ms 39044 KB Output is correct
28 Correct 32 ms 15884 KB Output is correct
29 Correct 162 ms 16524 KB Output is correct
30 Correct 370 ms 16764 KB Output is correct
31 Correct 165 ms 16636 KB Output is correct
32 Correct 244 ms 16740 KB Output is correct
33 Correct 1089 ms 16964 KB Output is correct
34 Correct 40 ms 15920 KB Output is correct
35 Correct 1122 ms 39464 KB Output is correct
36 Correct 862 ms 39804 KB Output is correct
37 Correct 1776 ms 39636 KB Output is correct
38 Correct 24 ms 15828 KB Output is correct
39 Correct 987 ms 45504 KB Output is correct
40 Correct 1320 ms 46188 KB Output is correct
41 Correct 1141 ms 45420 KB Output is correct
42 Correct 1131 ms 45552 KB Output is correct
43 Correct 28 ms 15884 KB Output is correct
44 Correct 833 ms 39064 KB Output is correct
45 Correct 1074 ms 38980 KB Output is correct
46 Correct 1391 ms 40264 KB Output is correct
47 Correct 1361 ms 40296 KB Output is correct
48 Execution timed out 3570 ms 40996 KB Time limit exceeded
49 Halted 0 ms 0 KB -