oj.uz

Submission #817879

# Submission time Handle Problem Language Result Execution time Memory
817879 2023-08-09T18:35:31 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
70 / 100
 3500 ms 47488 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 ;
	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 15828 KB Output is correct
2 Correct 31 ms 16600 KB Output is correct
3 Correct 29 ms 16728 KB Output is correct
4 Correct 28 ms 16644 KB Output is correct
5 Correct 27 ms 16860 KB Output is correct
6 Correct 34 ms 16716 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 31 ms 16600 KB Output is correct
3 Correct 29 ms 16728 KB Output is correct
4 Correct 28 ms 16644 KB Output is correct
5 Correct 27 ms 16860 KB Output is correct
6 Correct 34 ms 16716 KB Output is correct
7 Correct 31 ms 15800 KB Output is correct
8 Correct 190 ms 16580 KB Output is correct
9 Correct 474 ms 16792 KB Output is correct
10 Correct 236 ms 16692 KB Output is correct
11 Correct 250 ms 16824 KB Output is correct
12 Correct 1167 ms 17012 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 559 ms 39532 KB Output is correct
3 Correct 632 ms 39556 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 559 ms 39532 KB Output is correct
3 Correct 632 ms 39556 KB Output is correct
4 Correct 40 ms 15884 KB Output is correct
5 Correct 1156 ms 39564 KB Output is correct
6 Correct 848 ms 39940 KB Output is correct
7 Correct 1902 ms 39664 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15956 KB Output is correct
2 Correct 644 ms 45656 KB Output is correct
3 Correct 694 ms 45568 KB Output is correct
4 Correct 580 ms 47488 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15956 KB Output is correct
2 Correct 644 ms 45656 KB Output is correct
3 Correct 694 ms 45568 KB Output is correct
4 Correct 580 ms 47488 KB Output is correct
5 Correct 24 ms 15808 KB Output is correct
6 Correct 866 ms 45576 KB Output is correct
7 Correct 1389 ms 46148 KB Output is correct
8 Correct 1076 ms 45488 KB Output is correct
9 Correct 1074 ms 45480 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15908 KB Output is correct
2 Correct 381 ms 39068 KB Output is correct
3 Correct 739 ms 39080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15908 KB Output is correct
2 Correct 381 ms 39068 KB Output is correct
3 Correct 739 ms 39080 KB Output is correct
4 Correct 27 ms 15828 KB Output is correct
5 Correct 1014 ms 39112 KB Output is correct
6 Correct 966 ms 39020 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15816 KB Output is correct
2 Correct 697 ms 45560 KB Output is correct
3 Correct 672 ms 45752 KB Output is correct
4 Correct 500 ms 47308 KB Output is correct
5 Correct 24 ms 15872 KB Output is correct
6 Correct 378 ms 39056 KB Output is correct
7 Correct 726 ms 39176 KB Output is correct
8 Correct 929 ms 40380 KB Output is correct
9 Correct 879 ms 40440 KB Output is correct
10 Correct 1461 ms 41768 KB Output is correct
11 Correct 1537 ms 41672 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15816 KB Output is correct
2 Correct 697 ms 45560 KB Output is correct
3 Correct 672 ms 45752 KB Output is correct
4 Correct 500 ms 47308 KB Output is correct
5 Correct 24 ms 15872 KB Output is correct
6 Correct 378 ms 39056 KB Output is correct
7 Correct 726 ms 39176 KB Output is correct
8 Correct 929 ms 40380 KB Output is correct
9 Correct 879 ms 40440 KB Output is correct
10 Correct 1461 ms 41768 KB Output is correct
11 Correct 1537 ms 41672 KB Output is correct
12 Correct 24 ms 15896 KB Output is correct
13 Correct 989 ms 45616 KB Output is correct
14 Correct 1446 ms 46156 KB Output is correct
15 Correct 1331 ms 45380 KB Output is correct
16 Correct 1335 ms 45372 KB Output is correct
17 Correct 29 ms 15856 KB Output is correct
18 Correct 1108 ms 39084 KB Output is correct
19 Correct 1252 ms 39040 KB Output is correct
20 Correct 1243 ms 40296 KB Output is correct
21 Correct 1144 ms 40240 KB Output is correct
22 Execution timed out 3569 ms 41108 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 15852 KB Output is correct
2 Correct 28 ms 16608 KB Output is correct
3 Correct 30 ms 16724 KB Output is correct
4 Correct 28 ms 16696 KB Output is correct
5 Correct 27 ms 16792 KB Output is correct
6 Correct 31 ms 16724 KB Output is correct
7 Correct 24 ms 15824 KB Output is correct
8 Correct 509 ms 39740 KB Output is correct
9 Correct 569 ms 39652 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 647 ms 45600 KB Output is correct
12 Correct 671 ms 45684 KB Output is correct
13 Correct 520 ms 47276 KB Output is correct
14 Correct 23 ms 15892 KB Output is correct
15 Correct 384 ms 39032 KB Output is correct
16 Correct 695 ms 39168 KB Output is correct
17 Correct 924 ms 40344 KB Output is correct
18 Correct 1008 ms 40372 KB Output is correct
19 Correct 1825 ms 41868 KB Output is correct
20 Correct 1476 ms 41568 KB Output is correct
21 Correct 551 ms 39464 KB Output is correct
22 Correct 570 ms 39520 KB Output is correct
23 Correct 718 ms 40248 KB Output is correct
24 Correct 668 ms 40216 KB Output is correct
25 Correct 881 ms 40880 KB Output is correct
26 Correct 1010 ms 39024 KB Output is correct
27 Correct 873 ms 39004 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15852 KB Output is correct
2 Correct 28 ms 16608 KB Output is correct
3 Correct 30 ms 16724 KB Output is correct
4 Correct 28 ms 16696 KB Output is correct
5 Correct 27 ms 16792 KB Output is correct
6 Correct 31 ms 16724 KB Output is correct
7 Correct 24 ms 15824 KB Output is correct
8 Correct 509 ms 39740 KB Output is correct
9 Correct 569 ms 39652 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 647 ms 45600 KB Output is correct
12 Correct 671 ms 45684 KB Output is correct
13 Correct 520 ms 47276 KB Output is correct
14 Correct 23 ms 15892 KB Output is correct
15 Correct 384 ms 39032 KB Output is correct
16 Correct 695 ms 39168 KB Output is correct
17 Correct 924 ms 40344 KB Output is correct
18 Correct 1008 ms 40372 KB Output is correct
19 Correct 1825 ms 41868 KB Output is correct
20 Correct 1476 ms 41568 KB Output is correct
21 Correct 551 ms 39464 KB Output is correct
22 Correct 570 ms 39520 KB Output is correct
23 Correct 718 ms 40248 KB Output is correct
24 Correct 668 ms 40216 KB Output is correct
25 Correct 881 ms 40880 KB Output is correct
26 Correct 1010 ms 39024 KB Output is correct
27 Correct 873 ms 39004 KB Output is correct
28 Correct 31 ms 15964 KB Output is correct
29 Correct 185 ms 16572 KB Output is correct
30 Correct 494 ms 16716 KB Output is correct
31 Correct 204 ms 16576 KB Output is correct
32 Correct 246 ms 16804 KB Output is correct
33 Correct 1077 ms 16808 KB Output is correct
34 Correct 40 ms 15896 KB Output is correct
35 Correct 1029 ms 39600 KB Output is correct
36 Correct 726 ms 39916 KB Output is correct
37 Correct 2013 ms 39664 KB Output is correct
38 Correct 24 ms 15828 KB Output is correct
39 Correct 853 ms 45572 KB Output is correct
40 Correct 1344 ms 46148 KB Output is correct
41 Correct 1072 ms 45448 KB Output is correct
42 Correct 1049 ms 45452 KB Output is correct
43 Correct 27 ms 15884 KB Output is correct
44 Correct 1042 ms 39164 KB Output is correct
45 Correct 883 ms 39144 KB Output is correct
46 Correct 1249 ms 40212 KB Output is correct
47 Correct 1117 ms 40332 KB Output is correct
48 Execution timed out 3582 ms 41020 KB Time limit exceeded
49 Halted 0 ms 0 KB -