oj.uz

Submission #817877

# Submission time Handle Problem Language Result Execution time Memory
817877 2023-08-09T18:32:17 Z MohamedAhmed04 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 47344 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 23 ms 15824 KB Output is correct
2 Correct 33 ms 16648 KB Output is correct
3 Correct 37 ms 16788 KB Output is correct
4 Correct 29 ms 16692 KB Output is correct
5 Correct 27 ms 16852 KB Output is correct
6 Correct 31 ms 16768 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15824 KB Output is correct
2 Correct 33 ms 16648 KB Output is correct
3 Correct 37 ms 16788 KB Output is correct
4 Correct 29 ms 16692 KB Output is correct
5 Correct 27 ms 16852 KB Output is correct
6 Correct 31 ms 16768 KB Output is correct
7 Correct 39 ms 15884 KB Output is correct
8 Correct 189 ms 16584 KB Output is correct
9 Correct 470 ms 16776 KB Output is correct
10 Correct 218 ms 16564 KB Output is correct
11 Correct 250 ms 16812 KB Output is correct
12 Correct 1098 ms 16876 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15828 KB Output is correct
2 Correct 588 ms 39444 KB Output is correct
3 Correct 534 ms 39484 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15828 KB Output is correct
2 Correct 588 ms 39444 KB Output is correct
3 Correct 534 ms 39484 KB Output is correct
4 Correct 40 ms 15820 KB Output is correct
5 Correct 990 ms 39572 KB Output is correct
6 Correct 786 ms 39800 KB Output is correct
7 Correct 2193 ms 39612 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 660 ms 45664 KB Output is correct
3 Correct 686 ms 45644 KB Output is correct
4 Correct 578 ms 47248 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 660 ms 45664 KB Output is correct
3 Correct 686 ms 45644 KB Output is correct
4 Correct 578 ms 47248 KB Output is correct
5 Correct 24 ms 15876 KB Output is correct
6 Correct 852 ms 45560 KB Output is correct
7 Correct 1396 ms 46128 KB Output is correct
8 Correct 1006 ms 45476 KB Output is correct
9 Correct 1056 ms 45432 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 403 ms 38984 KB Output is correct
3 Correct 717 ms 39144 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 403 ms 38984 KB Output is correct
3 Correct 717 ms 39144 KB Output is correct
4 Correct 28 ms 15828 KB Output is correct
5 Correct 1036 ms 38976 KB Output is correct
6 Correct 874 ms 39044 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15872 KB Output is correct
2 Correct 659 ms 45584 KB Output is correct
3 Correct 670 ms 45688 KB Output is correct
4 Correct 520 ms 47344 KB Output is correct
5 Correct 21 ms 15876 KB Output is correct
6 Correct 368 ms 39056 KB Output is correct
7 Correct 991 ms 39048 KB Output is correct
8 Correct 1184 ms 40296 KB Output is correct
9 Correct 875 ms 40412 KB Output is correct
10 Correct 1578 ms 41876 KB Output is correct
11 Correct 2149 ms 41644 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15872 KB Output is correct
2 Correct 659 ms 45584 KB Output is correct
3 Correct 670 ms 45688 KB Output is correct
4 Correct 520 ms 47344 KB Output is correct
5 Correct 21 ms 15876 KB Output is correct
6 Correct 368 ms 39056 KB Output is correct
7 Correct 991 ms 39048 KB Output is correct
8 Correct 1184 ms 40296 KB Output is correct
9 Correct 875 ms 40412 KB Output is correct
10 Correct 1578 ms 41876 KB Output is correct
11 Correct 2149 ms 41644 KB Output is correct
12 Correct 24 ms 15828 KB Output is correct
13 Correct 941 ms 45556 KB Output is correct
14 Correct 1374 ms 46100 KB Output is correct
15 Correct 1177 ms 45440 KB Output is correct
16 Correct 1126 ms 45388 KB Output is correct
17 Correct 28 ms 15824 KB Output is correct
18 Correct 1026 ms 39080 KB Output is correct
19 Correct 1296 ms 38976 KB Output is correct
20 Correct 1729 ms 40316 KB Output is correct
21 Correct 1403 ms 40268 KB Output is correct
22 Execution timed out 3563 ms 41076 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 33 ms 16636 KB Output is correct
3 Correct 41 ms 16776 KB Output is correct
4 Correct 28 ms 16652 KB Output is correct
5 Correct 40 ms 16828 KB Output is correct
6 Correct 36 ms 16700 KB Output is correct
7 Correct 36 ms 15916 KB Output is correct
8 Correct 780 ms 39556 KB Output is correct
9 Correct 544 ms 39572 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 750 ms 45608 KB Output is correct
12 Correct 959 ms 45640 KB Output is correct
13 Correct 741 ms 47300 KB Output is correct
14 Correct 22 ms 15876 KB Output is correct
15 Correct 422 ms 38988 KB Output is correct
16 Correct 875 ms 39284 KB Output is correct
17 Correct 1079 ms 40328 KB Output is correct
18 Correct 1294 ms 40412 KB Output is correct
19 Correct 2611 ms 41932 KB Output is correct
20 Correct 1580 ms 41584 KB Output is correct
21 Correct 669 ms 39556 KB Output is correct
22 Correct 918 ms 39536 KB Output is correct
23 Correct 846 ms 40164 KB Output is correct
24 Correct 832 ms 40256 KB Output is correct
25 Correct 1273 ms 40988 KB Output is correct
26 Correct 1049 ms 39056 KB Output is correct
27 Correct 1039 ms 39060 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 33 ms 16636 KB Output is correct
3 Correct 41 ms 16776 KB Output is correct
4 Correct 28 ms 16652 KB Output is correct
5 Correct 40 ms 16828 KB Output is correct
6 Correct 36 ms 16700 KB Output is correct
7 Correct 36 ms 15916 KB Output is correct
8 Correct 780 ms 39556 KB Output is correct
9 Correct 544 ms 39572 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 750 ms 45608 KB Output is correct
12 Correct 959 ms 45640 KB Output is correct
13 Correct 741 ms 47300 KB Output is correct
14 Correct 22 ms 15876 KB Output is correct
15 Correct 422 ms 38988 KB Output is correct
16 Correct 875 ms 39284 KB Output is correct
17 Correct 1079 ms 40328 KB Output is correct
18 Correct 1294 ms 40412 KB Output is correct
19 Correct 2611 ms 41932 KB Output is correct
20 Correct 1580 ms 41584 KB Output is correct
21 Correct 669 ms 39556 KB Output is correct
22 Correct 918 ms 39536 KB Output is correct
23 Correct 846 ms 40164 KB Output is correct
24 Correct 832 ms 40256 KB Output is correct
25 Correct 1273 ms 40988 KB Output is correct
26 Correct 1049 ms 39056 KB Output is correct
27 Correct 1039 ms 39060 KB Output is correct
28 Correct 39 ms 15864 KB Output is correct
29 Correct 185 ms 16544 KB Output is correct
30 Correct 473 ms 16796 KB Output is correct
31 Correct 199 ms 16648 KB Output is correct
32 Correct 264 ms 16924 KB Output is correct
33 Correct 1202 ms 16808 KB Output is correct
34 Correct 47 ms 15900 KB Output is correct
35 Correct 1225 ms 39500 KB Output is correct
36 Correct 726 ms 39816 KB Output is correct
37 Correct 2605 ms 39628 KB Output is correct
38 Correct 30 ms 15828 KB Output is correct
39 Correct 871 ms 45484 KB Output is correct
40 Correct 1528 ms 46112 KB Output is correct
41 Correct 1348 ms 45380 KB Output is correct
42 Correct 1374 ms 45472 KB Output is correct
43 Correct 28 ms 15836 KB Output is correct
44 Correct 1051 ms 39044 KB Output is correct
45 Correct 1403 ms 38936 KB Output is correct
46 Correct 1873 ms 40220 KB Output is correct
47 Correct 1641 ms 40272 KB Output is correct
48 Execution timed out 3575 ms 40984 KB Time limit exceeded
49 Halted 0 ms 0 KB -