oj.uz

Submission #817846

# Submission time Handle Problem Language Result Execution time Memory
817846 2023-08-09T17:55:20 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 46536 KB 
#include <bits/stdc++.h>

using namespace std ;

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

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 24 ms 15880 KB Output is correct
2 Correct 28 ms 16548 KB Output is correct
3 Correct 30 ms 16652 KB Output is correct
4 Correct 29 ms 16628 KB Output is correct
5 Correct 28 ms 16728 KB Output is correct
6 Correct 31 ms 16596 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15880 KB Output is correct
2 Correct 28 ms 16548 KB Output is correct
3 Correct 30 ms 16652 KB Output is correct
4 Correct 29 ms 16628 KB Output is correct
5 Correct 28 ms 16728 KB Output is correct
6 Correct 31 ms 16596 KB Output is correct
7 Correct 30 ms 15804 KB Output is correct
8 Correct 1471 ms 16540 KB Output is correct
9 Execution timed out 3569 ms 17576 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15820 KB Output is correct
2 Correct 209 ms 39088 KB Output is correct
3 Correct 162 ms 39100 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15820 KB Output is correct
2 Correct 209 ms 39088 KB Output is correct
3 Correct 162 ms 39100 KB Output is correct
4 Correct 39 ms 15828 KB Output is correct
5 Execution timed out 3554 ms 37660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15880 KB Output is correct
2 Correct 207 ms 45212 KB Output is correct
3 Correct 160 ms 45108 KB Output is correct
4 Correct 169 ms 46524 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15880 KB Output is correct
2 Correct 207 ms 45212 KB Output is correct
3 Correct 160 ms 45108 KB Output is correct
4 Correct 169 ms 46524 KB Output is correct
5 Correct 26 ms 15888 KB Output is correct
6 Correct 2981 ms 45124 KB Output is correct
7 Execution timed out 3567 ms 46536 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 15828 KB Output is correct
2 Correct 127 ms 38580 KB Output is correct
3 Correct 235 ms 38660 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 127 ms 38580 KB Output is correct
3 Correct 235 ms 38660 KB Output is correct
4 Correct 28 ms 16724 KB Output is correct
5 Execution timed out 3509 ms 39728 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 15928 KB Output is correct
2 Correct 235 ms 45204 KB Output is correct
3 Correct 202 ms 45164 KB Output is correct
4 Correct 136 ms 46492 KB Output is correct
5 Correct 29 ms 15820 KB Output is correct
6 Correct 115 ms 38516 KB Output is correct
7 Correct 250 ms 38712 KB Output is correct
8 Correct 267 ms 41028 KB Output is correct
9 Correct 209 ms 41036 KB Output is correct
10 Correct 333 ms 42516 KB Output is correct
11 Correct 302 ms 42016 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15928 KB Output is correct
2 Correct 235 ms 45204 KB Output is correct
3 Correct 202 ms 45164 KB Output is correct
4 Correct 136 ms 46492 KB Output is correct
5 Correct 29 ms 15820 KB Output is correct
6 Correct 115 ms 38516 KB Output is correct
7 Correct 250 ms 38712 KB Output is correct
8 Correct 267 ms 41028 KB Output is correct
9 Correct 209 ms 41036 KB Output is correct
10 Correct 333 ms 42516 KB Output is correct
11 Correct 302 ms 42016 KB Output is correct
12 Correct 26 ms 16688 KB Output is correct
13 Correct 3121 ms 46212 KB Output is correct
14 Execution timed out 3564 ms 46484 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 15880 KB Output is correct
2 Correct 30 ms 16540 KB Output is correct
3 Correct 30 ms 16600 KB Output is correct
4 Correct 37 ms 16596 KB Output is correct
5 Correct 26 ms 16712 KB Output is correct
6 Correct 30 ms 16596 KB Output is correct
7 Correct 33 ms 15888 KB Output is correct
8 Correct 192 ms 39020 KB Output is correct
9 Correct 222 ms 39100 KB Output is correct
10 Correct 23 ms 15820 KB Output is correct
11 Correct 197 ms 45128 KB Output is correct
12 Correct 212 ms 45176 KB Output is correct
13 Correct 140 ms 46512 KB Output is correct
14 Correct 24 ms 15912 KB Output is correct
15 Correct 137 ms 38604 KB Output is correct
16 Correct 213 ms 38644 KB Output is correct
17 Correct 225 ms 41032 KB Output is correct
18 Correct 247 ms 41204 KB Output is correct
19 Correct 270 ms 42576 KB Output is correct
20 Correct 309 ms 41996 KB Output is correct
21 Correct 178 ms 40200 KB Output is correct
22 Correct 227 ms 40196 KB Output is correct
23 Correct 229 ms 40964 KB Output is correct
24 Correct 191 ms 40860 KB Output is correct
25 Correct 250 ms 41624 KB Output is correct
26 Correct 252 ms 39732 KB Output is correct
27 Correct 201 ms 39708 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15880 KB Output is correct
2 Correct 30 ms 16540 KB Output is correct
3 Correct 30 ms 16600 KB Output is correct
4 Correct 37 ms 16596 KB Output is correct
5 Correct 26 ms 16712 KB Output is correct
6 Correct 30 ms 16596 KB Output is correct
7 Correct 33 ms 15888 KB Output is correct
8 Correct 192 ms 39020 KB Output is correct
9 Correct 222 ms 39100 KB Output is correct
10 Correct 23 ms 15820 KB Output is correct
11 Correct 197 ms 45128 KB Output is correct
12 Correct 212 ms 45176 KB Output is correct
13 Correct 140 ms 46512 KB Output is correct
14 Correct 24 ms 15912 KB Output is correct
15 Correct 137 ms 38604 KB Output is correct
16 Correct 213 ms 38644 KB Output is correct
17 Correct 225 ms 41032 KB Output is correct
18 Correct 247 ms 41204 KB Output is correct
19 Correct 270 ms 42576 KB Output is correct
20 Correct 309 ms 41996 KB Output is correct
21 Correct 178 ms 40200 KB Output is correct
22 Correct 227 ms 40196 KB Output is correct
23 Correct 229 ms 40964 KB Output is correct
24 Correct 191 ms 40860 KB Output is correct
25 Correct 250 ms 41624 KB Output is correct
26 Correct 252 ms 39732 KB Output is correct
27 Correct 201 ms 39708 KB Output is correct
28 Correct 32 ms 16764 KB Output is correct
29 Correct 1339 ms 17664 KB Output is correct
30 Execution timed out 3582 ms 17616 KB Time limit exceeded
31 Halted 0 ms 0 KB -