oj.uz

Submission #817870

# Submission time Handle Problem Language Result Execution time Memory
817870 2023-08-09T18:23:39 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
100 / 100
 3486 ms 47360 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 21 ms 15828 KB Output is correct
2 Correct 27 ms 16580 KB Output is correct
3 Correct 30 ms 16784 KB Output is correct
4 Correct 28 ms 16676 KB Output is correct
5 Correct 27 ms 16772 KB Output is correct
6 Correct 31 ms 16696 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 27 ms 16580 KB Output is correct
3 Correct 30 ms 16784 KB Output is correct
4 Correct 28 ms 16676 KB Output is correct
5 Correct 27 ms 16772 KB Output is correct
6 Correct 31 ms 16696 KB Output is correct
7 Correct 31 ms 15916 KB Output is correct
8 Correct 185 ms 16572 KB Output is correct
9 Correct 460 ms 16800 KB Output is correct
10 Correct 199 ms 16640 KB Output is correct
11 Correct 252 ms 16816 KB Output is correct
12 Correct 1083 ms 16796 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 509 ms 39496 KB Output is correct
3 Correct 544 ms 39472 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 509 ms 39496 KB Output is correct
3 Correct 544 ms 39472 KB Output is correct
4 Correct 40 ms 15828 KB Output is correct
5 Correct 979 ms 39476 KB Output is correct
6 Correct 712 ms 39868 KB Output is correct
7 Correct 1897 ms 39672 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 648 ms 45564 KB Output is correct
3 Correct 680 ms 45688 KB Output is correct
4 Correct 603 ms 47300 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 648 ms 45564 KB Output is correct
3 Correct 680 ms 45688 KB Output is correct
4 Correct 603 ms 47300 KB Output is correct
5 Correct 24 ms 15828 KB Output is correct
6 Correct 829 ms 45520 KB Output is correct
7 Correct 1344 ms 46176 KB Output is correct
8 Correct 993 ms 45576 KB Output is correct
9 Correct 1002 ms 45488 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15800 KB Output is correct
2 Correct 370 ms 38968 KB Output is correct
3 Correct 695 ms 39160 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15800 KB Output is correct
2 Correct 370 ms 38968 KB Output is correct
3 Correct 695 ms 39160 KB Output is correct
4 Correct 28 ms 15888 KB Output is correct
5 Correct 983 ms 39260 KB Output is correct
6 Correct 885 ms 38972 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15852 KB Output is correct
2 Correct 674 ms 45644 KB Output is correct
3 Correct 651 ms 45680 KB Output is correct
4 Correct 571 ms 47360 KB Output is correct
5 Correct 28 ms 15856 KB Output is correct
6 Correct 368 ms 39016 KB Output is correct
7 Correct 733 ms 39140 KB Output is correct
8 Correct 839 ms 40384 KB Output is correct
9 Correct 918 ms 40412 KB Output is correct
10 Correct 1608 ms 41836 KB Output is correct
11 Correct 1687 ms 41736 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15852 KB Output is correct
2 Correct 674 ms 45644 KB Output is correct
3 Correct 651 ms 45680 KB Output is correct
4 Correct 571 ms 47360 KB Output is correct
5 Correct 28 ms 15856 KB Output is correct
6 Correct 368 ms 39016 KB Output is correct
7 Correct 733 ms 39140 KB Output is correct
8 Correct 839 ms 40384 KB Output is correct
9 Correct 918 ms 40412 KB Output is correct
10 Correct 1608 ms 41836 KB Output is correct
11 Correct 1687 ms 41736 KB Output is correct
12 Correct 25 ms 15836 KB Output is correct
13 Correct 856 ms 45520 KB Output is correct
14 Correct 1353 ms 46104 KB Output is correct
15 Correct 1016 ms 45656 KB Output is correct
16 Correct 1016 ms 45500 KB Output is correct
17 Correct 28 ms 15828 KB Output is correct
18 Correct 999 ms 39208 KB Output is correct
19 Correct 871 ms 38980 KB Output is correct
20 Correct 1277 ms 40224 KB Output is correct
21 Correct 1103 ms 40220 KB Output is correct
22 Correct 3483 ms 41220 KB Output is correct
23 Correct 2547 ms 45984 KB Output is correct
24 Correct 1710 ms 46104 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 27 ms 16696 KB Output is correct
3 Correct 30 ms 16740 KB Output is correct
4 Correct 28 ms 16712 KB Output is correct
5 Correct 27 ms 16896 KB Output is correct
6 Correct 31 ms 16664 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 502 ms 39540 KB Output is correct
9 Correct 557 ms 39588 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 654 ms 45708 KB Output is correct
12 Correct 639 ms 45576 KB Output is correct
13 Correct 567 ms 47280 KB Output is correct
14 Correct 25 ms 15820 KB Output is correct
15 Correct 366 ms 38960 KB Output is correct
16 Correct 708 ms 39216 KB Output is correct
17 Correct 832 ms 40420 KB Output is correct
18 Correct 881 ms 40352 KB Output is correct
19 Correct 1528 ms 41888 KB Output is correct
20 Correct 1540 ms 41704 KB Output is correct
21 Correct 520 ms 39616 KB Output is correct
22 Correct 582 ms 39472 KB Output is correct
23 Correct 679 ms 40208 KB Output is correct
24 Correct 717 ms 40172 KB Output is correct
25 Correct 844 ms 40976 KB Output is correct
26 Correct 929 ms 39076 KB Output is correct
27 Correct 891 ms 38936 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 27 ms 16696 KB Output is correct
3 Correct 30 ms 16740 KB Output is correct
4 Correct 28 ms 16712 KB Output is correct
5 Correct 27 ms 16896 KB Output is correct
6 Correct 31 ms 16664 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 502 ms 39540 KB Output is correct
9 Correct 557 ms 39588 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 654 ms 45708 KB Output is correct
12 Correct 639 ms 45576 KB Output is correct
13 Correct 567 ms 47280 KB Output is correct
14 Correct 25 ms 15820 KB Output is correct
15 Correct 366 ms 38960 KB Output is correct
16 Correct 708 ms 39216 KB Output is correct
17 Correct 832 ms 40420 KB Output is correct
18 Correct 881 ms 40352 KB Output is correct
19 Correct 1528 ms 41888 KB Output is correct
20 Correct 1540 ms 41704 KB Output is correct
21 Correct 520 ms 39616 KB Output is correct
22 Correct 582 ms 39472 KB Output is correct
23 Correct 679 ms 40208 KB Output is correct
24 Correct 717 ms 40172 KB Output is correct
25 Correct 844 ms 40976 KB Output is correct
26 Correct 929 ms 39076 KB Output is correct
27 Correct 891 ms 38936 KB Output is correct
28 Correct 31 ms 15828 KB Output is correct
29 Correct 189 ms 16508 KB Output is correct
30 Correct 460 ms 16756 KB Output is correct
31 Correct 197 ms 16628 KB Output is correct
32 Correct 250 ms 16848 KB Output is correct
33 Correct 1075 ms 16792 KB Output is correct
34 Correct 40 ms 15840 KB Output is correct
35 Correct 970 ms 39640 KB Output is correct
36 Correct 723 ms 39848 KB Output is correct
37 Correct 1912 ms 39684 KB Output is correct
38 Correct 28 ms 15828 KB Output is correct
39 Correct 839 ms 45508 KB Output is correct
40 Correct 1385 ms 46176 KB Output is correct
41 Correct 1008 ms 45488 KB Output is correct
42 Correct 996 ms 45440 KB Output is correct
43 Correct 27 ms 15844 KB Output is correct
44 Correct 994 ms 39008 KB Output is correct
45 Correct 933 ms 39024 KB Output is correct
46 Correct 1263 ms 40332 KB Output is correct
47 Correct 1078 ms 40232 KB Output is correct
48 Correct 3486 ms 41044 KB Output is correct
49 Correct 2482 ms 43000 KB Output is correct
50 Correct 1684 ms 42912 KB Output is correct
51 Correct 1329 ms 39780 KB Output is correct
52 Correct 1932 ms 39756 KB Output is correct
53 Correct 1981 ms 39620 KB Output is correct
54 Correct 717 ms 39836 KB Output is correct
55 Correct 2219 ms 39924 KB Output is correct
56 Correct 817 ms 40272 KB Output is correct
57 Correct 1123 ms 40784 KB Output is correct
58 Correct 1337 ms 38844 KB Output is correct
59 Correct 964 ms 39096 KB Output is correct