oj.uz

Submission #817861

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

using namespace std ;

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

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 ;

void dfs(int node , int par)
{
	in[node] = ++tim ;
	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(int i = 1 ; i <= n ; ++i)
	{
		if(vis[i])
			continue ;
		dfs2(i , i) ;
		dfs3(i , i , 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 16528 KB Output is correct
3 Correct 29 ms 16680 KB Output is correct
4 Correct 40 ms 16576 KB Output is correct
5 Correct 27 ms 16764 KB Output is correct
6 Correct 30 ms 16596 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 27 ms 16528 KB Output is correct
3 Correct 29 ms 16680 KB Output is correct
4 Correct 40 ms 16576 KB Output is correct
5 Correct 27 ms 16764 KB Output is correct
6 Correct 30 ms 16596 KB Output is correct
7 Correct 29 ms 15896 KB Output is correct
8 Correct 1275 ms 16536 KB Output is correct
9 Execution timed out 3565 ms 17672 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15892 KB Output is correct
2 Correct 197 ms 39024 KB Output is correct
3 Correct 251 ms 39008 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15892 KB Output is correct
2 Correct 197 ms 39024 KB Output is correct
3 Correct 251 ms 39008 KB Output is correct
4 Correct 38 ms 15816 KB Output is correct
5 Execution timed out 3581 ms 38680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15848 KB Output is correct
2 Correct 231 ms 45212 KB Output is correct
3 Correct 198 ms 45128 KB Output is correct
4 Correct 146 ms 46572 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15848 KB Output is correct
2 Correct 231 ms 45212 KB Output is correct
3 Correct 198 ms 45128 KB Output is correct
4 Correct 146 ms 46572 KB Output is correct
5 Correct 24 ms 15784 KB Output is correct
6 Correct 2166 ms 45228 KB Output is correct
7 Execution timed out 3575 ms 44004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15860 KB Output is correct
2 Correct 128 ms 38560 KB Output is correct
3 Correct 208 ms 38644 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15860 KB Output is correct
2 Correct 128 ms 38560 KB Output is correct
3 Correct 208 ms 38644 KB Output is correct
4 Correct 29 ms 15804 KB Output is correct
5 Execution timed out 3582 ms 38480 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 198 ms 45148 KB Output is correct
3 Correct 179 ms 45224 KB Output is correct
4 Correct 143 ms 46560 KB Output is correct
5 Correct 22 ms 15872 KB Output is correct
6 Correct 124 ms 38520 KB Output is correct
7 Correct 214 ms 38664 KB Output is correct
8 Correct 222 ms 39852 KB Output is correct
9 Correct 232 ms 39956 KB Output is correct
10 Correct 299 ms 41320 KB Output is correct
11 Correct 296 ms 40784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 198 ms 45148 KB Output is correct
3 Correct 179 ms 45224 KB Output is correct
4 Correct 143 ms 46560 KB Output is correct
5 Correct 22 ms 15872 KB Output is correct
6 Correct 124 ms 38520 KB Output is correct
7 Correct 214 ms 38664 KB Output is correct
8 Correct 222 ms 39852 KB Output is correct
9 Correct 232 ms 39956 KB Output is correct
10 Correct 299 ms 41320 KB Output is correct
11 Correct 296 ms 40784 KB Output is correct
12 Correct 29 ms 15900 KB Output is correct
13 Correct 2180 ms 45120 KB Output is correct
14 Execution timed out 3559 ms 43944 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15820 KB Output is correct
2 Correct 27 ms 16552 KB Output is correct
3 Correct 30 ms 16708 KB Output is correct
4 Correct 27 ms 16664 KB Output is correct
5 Correct 26 ms 16724 KB Output is correct
6 Correct 31 ms 16620 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 180 ms 39104 KB Output is correct
9 Correct 168 ms 39100 KB Output is correct
10 Correct 21 ms 15868 KB Output is correct
11 Correct 186 ms 45140 KB Output is correct
12 Correct 176 ms 45188 KB Output is correct
13 Correct 154 ms 46616 KB Output is correct
14 Correct 22 ms 15828 KB Output is correct
15 Correct 126 ms 38536 KB Output is correct
16 Correct 223 ms 38680 KB Output is correct
17 Correct 233 ms 39916 KB Output is correct
18 Correct 221 ms 39952 KB Output is correct
19 Correct 289 ms 41336 KB Output is correct
20 Correct 317 ms 40872 KB Output is correct
21 Correct 180 ms 39028 KB Output is correct
22 Correct 220 ms 39048 KB Output is correct
23 Correct 193 ms 39816 KB Output is correct
24 Correct 185 ms 39732 KB Output is correct
25 Correct 221 ms 40500 KB Output is correct
26 Correct 223 ms 38604 KB Output is correct
27 Correct 211 ms 38588 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15820 KB Output is correct
2 Correct 27 ms 16552 KB Output is correct
3 Correct 30 ms 16708 KB Output is correct
4 Correct 27 ms 16664 KB Output is correct
5 Correct 26 ms 16724 KB Output is correct
6 Correct 31 ms 16620 KB Output is correct
7 Correct 24 ms 15828 KB Output is correct
8 Correct 180 ms 39104 KB Output is correct
9 Correct 168 ms 39100 KB Output is correct
10 Correct 21 ms 15868 KB Output is correct
11 Correct 186 ms 45140 KB Output is correct
12 Correct 176 ms 45188 KB Output is correct
13 Correct 154 ms 46616 KB Output is correct
14 Correct 22 ms 15828 KB Output is correct
15 Correct 126 ms 38536 KB Output is correct
16 Correct 223 ms 38680 KB Output is correct
17 Correct 233 ms 39916 KB Output is correct
18 Correct 221 ms 39952 KB Output is correct
19 Correct 289 ms 41336 KB Output is correct
20 Correct 317 ms 40872 KB Output is correct
21 Correct 180 ms 39028 KB Output is correct
22 Correct 220 ms 39048 KB Output is correct
23 Correct 193 ms 39816 KB Output is correct
24 Correct 185 ms 39732 KB Output is correct
25 Correct 221 ms 40500 KB Output is correct
26 Correct 223 ms 38604 KB Output is correct
27 Correct 211 ms 38588 KB Output is correct
28 Correct 31 ms 15808 KB Output is correct
29 Correct 1268 ms 16492 KB Output is correct
30 Execution timed out 3568 ms 17624 KB Time limit exceeded
31 Halted 0 ms 0 KB -