oj.uz

Submission #817840

# Submission time Handle Problem Language Result Execution time Memory
817840 2023-08-09T17:46:27 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
12.5 / 100
 3500 ms 47968 KB 
#include <bits/stdc++.h>

using namespace std ;

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

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 16696 KB Output is correct
2 Correct 32 ms 17236 KB Output is correct
3 Correct 33 ms 17304 KB Output is correct
4 Correct 38 ms 17360 KB Output is correct
5 Correct 29 ms 17396 KB Output is correct
6 Correct 33 ms 17384 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16696 KB Output is correct
2 Correct 32 ms 17236 KB Output is correct
3 Correct 33 ms 17304 KB Output is correct
4 Correct 38 ms 17360 KB Output is correct
5 Correct 29 ms 17396 KB Output is correct
6 Correct 33 ms 17384 KB Output is correct
7 Correct 32 ms 16452 KB Output is correct
8 Incorrect 56 ms 17536 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16816 KB Output is correct
2 Correct 2568 ms 40196 KB Output is correct
3 Correct 3028 ms 39776 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16816 KB Output is correct
2 Correct 2568 ms 40196 KB Output is correct
3 Correct 3028 ms 39776 KB Output is correct
4 Correct 39 ms 16596 KB Output is correct
5 Correct 2749 ms 39788 KB Output is correct
6 Correct 2509 ms 40988 KB Output is correct
7 Correct 2728 ms 41096 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16716 KB Output is correct
2 Correct 3494 ms 46104 KB Output is correct
3 Correct 3402 ms 46228 KB Output is correct
4 Correct 2712 ms 47968 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16716 KB Output is correct
2 Correct 3494 ms 46104 KB Output is correct
3 Correct 3402 ms 46228 KB Output is correct
4 Correct 2712 ms 47968 KB Output is correct
5 Correct 26 ms 16364 KB Output is correct
6 Execution timed out 3501 ms 46128 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16816 KB Output is correct
2 Correct 1827 ms 39140 KB Output is correct
3 Execution timed out 3557 ms 39480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16816 KB Output is correct
2 Correct 1827 ms 39140 KB Output is correct
3 Execution timed out 3557 ms 39480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16752 KB Output is correct
2 Correct 3461 ms 46104 KB Output is correct
3 Correct 3455 ms 46228 KB Output is correct
4 Correct 2830 ms 47892 KB Output is correct
5 Correct 23 ms 16736 KB Output is correct
6 Correct 1821 ms 39580 KB Output is correct
7 Execution timed out 3591 ms 39500 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16752 KB Output is correct
2 Correct 3461 ms 46104 KB Output is correct
3 Correct 3455 ms 46228 KB Output is correct
4 Correct 2830 ms 47892 KB Output is correct
5 Correct 23 ms 16736 KB Output is correct
6 Correct 1821 ms 39580 KB Output is correct
7 Execution timed out 3591 ms 39500 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16716 KB Output is correct
2 Correct 33 ms 17280 KB Output is correct
3 Correct 34 ms 17356 KB Output is correct
4 Correct 33 ms 17352 KB Output is correct
5 Correct 30 ms 17492 KB Output is correct
6 Correct 34 ms 17268 KB Output is correct
7 Correct 25 ms 16468 KB Output is correct
8 Correct 2520 ms 39700 KB Output is correct
9 Correct 2531 ms 40104 KB Output is correct
10 Correct 22 ms 16716 KB Output is correct
11 Correct 3456 ms 46380 KB Output is correct
12 Correct 3478 ms 46228 KB Output is correct
13 Correct 2710 ms 47952 KB Output is correct
14 Correct 23 ms 16744 KB Output is correct
15 Correct 1840 ms 39564 KB Output is correct
16 Execution timed out 3558 ms 39204 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16716 KB Output is correct
2 Correct 33 ms 17280 KB Output is correct
3 Correct 34 ms 17356 KB Output is correct
4 Correct 33 ms 17352 KB Output is correct
5 Correct 30 ms 17492 KB Output is correct
6 Correct 34 ms 17268 KB Output is correct
7 Correct 25 ms 16468 KB Output is correct
8 Correct 2520 ms 39700 KB Output is correct
9 Correct 2531 ms 40104 KB Output is correct
10 Correct 22 ms 16716 KB Output is correct
11 Correct 3456 ms 46380 KB Output is correct
12 Correct 3478 ms 46228 KB Output is correct
13 Correct 2710 ms 47952 KB Output is correct
14 Correct 23 ms 16744 KB Output is correct
15 Correct 1840 ms 39564 KB Output is correct
16 Execution timed out 3558 ms 39204 KB Time limit exceeded
17 Halted 0 ms 0 KB -