Submission #817871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
817871	2023-08-09T18:26:03 Z	MohamedAhmed04	Inside information (BOI21_servers)	C++14	82.5 / 100	3500 ms	47380 KB

servers

#include <bits/stdc++.h>

using namespace std ;

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

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	15828 KB	Output is correct
2	Correct	27 ms	16596 KB	Output is correct
3	Correct	30 ms	16680 KB	Output is correct
4	Correct	34 ms	16764 KB	Output is correct
5	Correct	27 ms	16860 KB	Output is correct
6	Correct	31 ms	16680 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	15828 KB	Output is correct
2	Correct	27 ms	16596 KB	Output is correct
3	Correct	30 ms	16680 KB	Output is correct
4	Correct	34 ms	16764 KB	Output is correct
5	Correct	27 ms	16860 KB	Output is correct
6	Correct	31 ms	16680 KB	Output is correct
7	Correct	34 ms	15892 KB	Output is correct
8	Correct	174 ms	16560 KB	Output is correct
9	Correct	457 ms	16752 KB	Output is correct
10	Correct	190 ms	16672 KB	Output is correct
11	Correct	97 ms	16768 KB	Output is correct
12	Correct	592 ms	16760 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	15856 KB	Output is correct
2	Correct	570 ms	39496 KB	Output is correct
3	Correct	586 ms	39560 KB	Output is correct

Subtask #4
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	15856 KB	Output is correct
2	Correct	570 ms	39496 KB	Output is correct
3	Correct	586 ms	39560 KB	Output is correct
4	Correct	39 ms	15812 KB	Output is correct
5	Correct	985 ms	39524 KB	Output is correct
6	Correct	726 ms	40112 KB	Output is correct
7	Correct	1774 ms	39668 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	706 ms	45676 KB	Output is correct
3	Correct	702 ms	45700 KB	Output is correct
4	Correct	573 ms	47304 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	706 ms	45676 KB	Output is correct
3	Correct	702 ms	45700 KB	Output is correct
4	Correct	573 ms	47304 KB	Output is correct
5	Correct	24 ms	15896 KB	Output is correct
6	Correct	869 ms	45492 KB	Output is correct
7	Correct	1330 ms	46260 KB	Output is correct
8	Correct	1039 ms	45388 KB	Output is correct
9	Correct	1036 ms	45568 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	15928 KB	Output is correct
2	Correct	396 ms	39056 KB	Output is correct
3	Correct	778 ms	39136 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	15928 KB	Output is correct
2	Correct	396 ms	39056 KB	Output is correct
3	Correct	778 ms	39136 KB	Output is correct
4	Correct	27 ms	15828 KB	Output is correct
5	Correct	611 ms	39088 KB	Output is correct
6	Correct	925 ms	39076 KB	Output is correct

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	15828 KB	Output is correct
2	Correct	750 ms	45660 KB	Output is correct
3	Correct	702 ms	45752 KB	Output is correct
4	Correct	544 ms	47380 KB	Output is correct
5	Correct	22 ms	15840 KB	Output is correct
6	Correct	387 ms	39008 KB	Output is correct
7	Correct	775 ms	39084 KB	Output is correct
8	Correct	937 ms	40328 KB	Output is correct
9	Correct	950 ms	40376 KB	Output is correct
10	Correct	1696 ms	41776 KB	Output is correct
11	Correct	1694 ms	41684 KB	Output is correct

Subtask #10
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	15828 KB	Output is correct
2	Correct	750 ms	45660 KB	Output is correct
3	Correct	702 ms	45752 KB	Output is correct
4	Correct	544 ms	47380 KB	Output is correct
5	Correct	22 ms	15840 KB	Output is correct
6	Correct	387 ms	39008 KB	Output is correct
7	Correct	775 ms	39084 KB	Output is correct
8	Correct	937 ms	40328 KB	Output is correct
9	Correct	950 ms	40376 KB	Output is correct
10	Correct	1696 ms	41776 KB	Output is correct
11	Correct	1694 ms	41684 KB	Output is correct
12	Correct	24 ms	15828 KB	Output is correct
13	Correct	900 ms	45540 KB	Output is correct
14	Correct	1350 ms	46276 KB	Output is correct
15	Correct	1028 ms	45380 KB	Output is correct
16	Correct	1032 ms	45492 KB	Output is correct
17	Correct	28 ms	15804 KB	Output is correct
18	Correct	679 ms	39080 KB	Output is correct
19	Correct	943 ms	39172 KB	Output is correct
20	Correct	1041 ms	40376 KB	Output is correct
21	Correct	1186 ms	40356 KB	Output is correct
22	Correct	3433 ms	41204 KB	Output is correct
23	Correct	2554 ms	43040 KB	Output is correct
24	Correct	1757 ms	42784 KB	Output is correct

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	15892 KB	Output is correct
2	Correct	29 ms	16656 KB	Output is correct
3	Correct	30 ms	16780 KB	Output is correct
4	Correct	29 ms	16668 KB	Output is correct
5	Correct	27 ms	16852 KB	Output is correct
6	Correct	31 ms	16728 KB	Output is correct
7	Correct	23 ms	15924 KB	Output is correct
8	Correct	592 ms	39572 KB	Output is correct
9	Correct	542 ms	39512 KB	Output is correct
10	Correct	21 ms	15896 KB	Output is correct
11	Correct	693 ms	45640 KB	Output is correct
12	Correct	706 ms	45684 KB	Output is correct
13	Correct	581 ms	47300 KB	Output is correct
14	Correct	22 ms	15828 KB	Output is correct
15	Correct	401 ms	39052 KB	Output is correct
16	Correct	758 ms	39148 KB	Output is correct
17	Correct	951 ms	40268 KB	Output is correct
18	Correct	964 ms	40336 KB	Output is correct
19	Correct	1818 ms	41936 KB	Output is correct
20	Correct	2180 ms	41572 KB	Output is correct
21	Correct	787 ms	39560 KB	Output is correct
22	Correct	767 ms	39460 KB	Output is correct
23	Correct	1078 ms	40276 KB	Output is correct
24	Correct	1018 ms	40172 KB	Output is correct
25	Correct	1388 ms	40888 KB	Output is correct
26	Correct	1103 ms	39052 KB	Output is correct
27	Correct	1004 ms	39028 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	15892 KB	Output is correct
2	Correct	29 ms	16656 KB	Output is correct
3	Correct	30 ms	16780 KB	Output is correct
4	Correct	29 ms	16668 KB	Output is correct
5	Correct	27 ms	16852 KB	Output is correct
6	Correct	31 ms	16728 KB	Output is correct
7	Correct	23 ms	15924 KB	Output is correct
8	Correct	592 ms	39572 KB	Output is correct
9	Correct	542 ms	39512 KB	Output is correct
10	Correct	21 ms	15896 KB	Output is correct
11	Correct	693 ms	45640 KB	Output is correct
12	Correct	706 ms	45684 KB	Output is correct
13	Correct	581 ms	47300 KB	Output is correct
14	Correct	22 ms	15828 KB	Output is correct
15	Correct	401 ms	39052 KB	Output is correct
16	Correct	758 ms	39148 KB	Output is correct
17	Correct	951 ms	40268 KB	Output is correct
18	Correct	964 ms	40336 KB	Output is correct
19	Correct	1818 ms	41936 KB	Output is correct
20	Correct	2180 ms	41572 KB	Output is correct
21	Correct	787 ms	39560 KB	Output is correct
22	Correct	767 ms	39460 KB	Output is correct
23	Correct	1078 ms	40276 KB	Output is correct
24	Correct	1018 ms	40172 KB	Output is correct
25	Correct	1388 ms	40888 KB	Output is correct
26	Correct	1103 ms	39052 KB	Output is correct
27	Correct	1004 ms	39028 KB	Output is correct
28	Correct	41 ms	15828 KB	Output is correct
29	Correct	175 ms	16524 KB	Output is correct
30	Correct	448 ms	16804 KB	Output is correct
31	Correct	186 ms	16676 KB	Output is correct
32	Correct	111 ms	16816 KB	Output is correct
33	Correct	593 ms	16800 KB	Output is correct
34	Correct	40 ms	15928 KB	Output is correct
35	Correct	1074 ms	39516 KB	Output is correct
36	Correct	793 ms	39764 KB	Output is correct
37	Correct	1897 ms	39676 KB	Output is correct
38	Correct	25 ms	15828 KB	Output is correct
39	Correct	915 ms	45472 KB	Output is correct
40	Correct	1447 ms	46144 KB	Output is correct
41	Correct	1018 ms	45440 KB	Output is correct
42	Correct	1069 ms	45564 KB	Output is correct
43	Correct	29 ms	15844 KB	Output is correct
44	Correct	623 ms	39064 KB	Output is correct
45	Correct	1156 ms	39124 KB	Output is correct
46	Correct	1058 ms	40272 KB	Output is correct
47	Correct	1197 ms	40348 KB	Output is correct
48	Execution timed out	3547 ms	41080 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-

Submission #817871

Compilation message