oj.uz

Submission #817868

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

using namespace std ;

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

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 37 ms 15796 KB Output is correct
2 Correct 43 ms 16640 KB Output is correct
3 Correct 40 ms 16804 KB Output is correct
4 Correct 46 ms 16724 KB Output is correct
5 Correct 29 ms 16868 KB Output is correct
6 Correct 32 ms 16716 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15796 KB Output is correct
2 Correct 43 ms 16640 KB Output is correct
3 Correct 40 ms 16804 KB Output is correct
4 Correct 46 ms 16724 KB Output is correct
5 Correct 29 ms 16868 KB Output is correct
6 Correct 32 ms 16716 KB Output is correct
7 Correct 32 ms 15848 KB Output is correct
8 Correct 223 ms 16652 KB Output is correct
9 Correct 626 ms 16692 KB Output is correct
10 Correct 250 ms 16664 KB Output is correct
11 Correct 320 ms 16704 KB Output is correct
12 Correct 1363 ms 16912 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15820 KB Output is correct
2 Correct 487 ms 39484 KB Output is correct
3 Correct 555 ms 39508 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15820 KB Output is correct
2 Correct 487 ms 39484 KB Output is correct
3 Correct 555 ms 39508 KB Output is correct
4 Correct 41 ms 15820 KB Output is correct
5 Correct 1159 ms 39492 KB Output is correct
6 Correct 806 ms 39760 KB Output is correct
7 Correct 2239 ms 39572 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15828 KB Output is correct
2 Correct 620 ms 45736 KB Output is correct
3 Correct 595 ms 45628 KB Output is correct
4 Correct 469 ms 47340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15828 KB Output is correct
2 Correct 620 ms 45736 KB Output is correct
3 Correct 595 ms 45628 KB Output is correct
4 Correct 469 ms 47340 KB Output is correct
5 Correct 25 ms 15896 KB Output is correct
6 Correct 846 ms 45488 KB Output is correct
7 Correct 1497 ms 46132 KB Output is correct
8 Correct 1032 ms 45504 KB Output is correct
9 Correct 1092 ms 45544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15820 KB Output is correct
2 Correct 345 ms 39004 KB Output is correct
3 Correct 754 ms 39148 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15820 KB Output is correct
2 Correct 345 ms 39004 KB Output is correct
3 Correct 754 ms 39148 KB Output is correct
4 Correct 27 ms 15916 KB Output is correct
5 Correct 786 ms 39020 KB Output is correct
6 Correct 1106 ms 39068 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15900 KB Output is correct
2 Correct 742 ms 45568 KB Output is correct
3 Correct 696 ms 45608 KB Output is correct
4 Correct 565 ms 47308 KB Output is correct
5 Correct 23 ms 15908 KB Output is correct
6 Correct 369 ms 38956 KB Output is correct
7 Correct 788 ms 39172 KB Output is correct
8 Correct 986 ms 40356 KB Output is correct
9 Correct 909 ms 40344 KB Output is correct
10 Correct 1552 ms 41840 KB Output is correct
11 Correct 1408 ms 41556 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15900 KB Output is correct
2 Correct 742 ms 45568 KB Output is correct
3 Correct 696 ms 45608 KB Output is correct
4 Correct 565 ms 47308 KB Output is correct
5 Correct 23 ms 15908 KB Output is correct
6 Correct 369 ms 38956 KB Output is correct
7 Correct 788 ms 39172 KB Output is correct
8 Correct 986 ms 40356 KB Output is correct
9 Correct 909 ms 40344 KB Output is correct
10 Correct 1552 ms 41840 KB Output is correct
11 Correct 1408 ms 41556 KB Output is correct
12 Correct 25 ms 15828 KB Output is correct
13 Correct 893 ms 45580 KB Output is correct
14 Correct 1504 ms 46132 KB Output is correct
15 Correct 1038 ms 45472 KB Output is correct
16 Correct 1092 ms 45460 KB Output is correct
17 Correct 37 ms 15788 KB Output is correct
18 Correct 730 ms 39032 KB Output is correct
19 Correct 883 ms 39024 KB Output is correct
20 Correct 1102 ms 40260 KB Output is correct
21 Correct 1112 ms 40308 KB Output is correct
22 Execution timed out 3559 ms 41072 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15888 KB Output is correct
2 Correct 27 ms 16676 KB Output is correct
3 Correct 31 ms 16668 KB Output is correct
4 Correct 27 ms 16752 KB Output is correct
5 Correct 27 ms 16840 KB Output is correct
6 Correct 32 ms 16728 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 707 ms 39480 KB Output is correct
9 Correct 529 ms 39640 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 592 ms 45624 KB Output is correct
12 Correct 583 ms 45644 KB Output is correct
13 Correct 521 ms 47408 KB Output is correct
14 Correct 23 ms 15900 KB Output is correct
15 Correct 349 ms 39196 KB Output is correct
16 Correct 740 ms 39224 KB Output is correct
17 Correct 769 ms 40388 KB Output is correct
18 Correct 842 ms 40440 KB Output is correct
19 Correct 1409 ms 41968 KB Output is correct
20 Correct 1417 ms 41580 KB Output is correct
21 Correct 519 ms 39540 KB Output is correct
22 Correct 537 ms 39528 KB Output is correct
23 Correct 697 ms 40180 KB Output is correct
24 Correct 695 ms 40148 KB Output is correct
25 Correct 871 ms 40884 KB Output is correct
26 Correct 904 ms 39140 KB Output is correct
27 Correct 866 ms 39144 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15888 KB Output is correct
2 Correct 27 ms 16676 KB Output is correct
3 Correct 31 ms 16668 KB Output is correct
4 Correct 27 ms 16752 KB Output is correct
5 Correct 27 ms 16840 KB Output is correct
6 Correct 32 ms 16728 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 707 ms 39480 KB Output is correct
9 Correct 529 ms 39640 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 592 ms 45624 KB Output is correct
12 Correct 583 ms 45644 KB Output is correct
13 Correct 521 ms 47408 KB Output is correct
14 Correct 23 ms 15900 KB Output is correct
15 Correct 349 ms 39196 KB Output is correct
16 Correct 740 ms 39224 KB Output is correct
17 Correct 769 ms 40388 KB Output is correct
18 Correct 842 ms 40440 KB Output is correct
19 Correct 1409 ms 41968 KB Output is correct
20 Correct 1417 ms 41580 KB Output is correct
21 Correct 519 ms 39540 KB Output is correct
22 Correct 537 ms 39528 KB Output is correct
23 Correct 697 ms 40180 KB Output is correct
24 Correct 695 ms 40148 KB Output is correct
25 Correct 871 ms 40884 KB Output is correct
26 Correct 904 ms 39140 KB Output is correct
27 Correct 866 ms 39144 KB Output is correct
28 Correct 32 ms 15892 KB Output is correct
29 Correct 213 ms 16588 KB Output is correct
30 Correct 581 ms 17000 KB Output is correct
31 Correct 238 ms 16644 KB Output is correct
32 Correct 331 ms 17128 KB Output is correct
33 Correct 1324 ms 16920 KB Output is correct
34 Correct 40 ms 15920 KB Output is correct
35 Correct 1107 ms 39612 KB Output is correct
36 Correct 731 ms 39776 KB Output is correct
37 Correct 2101 ms 39668 KB Output is correct
38 Correct 24 ms 15828 KB Output is correct
39 Correct 819 ms 45612 KB Output is correct
40 Correct 1421 ms 46184 KB Output is correct
41 Correct 1020 ms 45416 KB Output is correct
42 Correct 1012 ms 45584 KB Output is correct
43 Correct 28 ms 15796 KB Output is correct
44 Correct 746 ms 39308 KB Output is correct
45 Correct 870 ms 39208 KB Output is correct
46 Correct 989 ms 40404 KB Output is correct
47 Correct 1046 ms 40260 KB Output is correct
48 Execution timed out 3569 ms 41296 KB Time limit exceeded
49 Halted 0 ms 0 KB -