oj.uz

Submission #817856

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

using namespace std ;

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

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 32 ms 16720 KB Output is correct
2 Correct 35 ms 17972 KB Output is correct
3 Correct 30 ms 18044 KB Output is correct
4 Correct 29 ms 18128 KB Output is correct
5 Correct 27 ms 18260 KB Output is correct
6 Correct 32 ms 18120 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16720 KB Output is correct
2 Correct 35 ms 17972 KB Output is correct
3 Correct 30 ms 18044 KB Output is correct
4 Correct 29 ms 18128 KB Output is correct
5 Correct 27 ms 18260 KB Output is correct
6 Correct 32 ms 18120 KB Output is correct
7 Correct 30 ms 16744 KB Output is correct
8 Incorrect 610 ms 17824 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 16724 KB Output is correct
2 Correct 245 ms 41684 KB Output is correct
3 Correct 237 ms 41300 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16724 KB Output is correct
2 Correct 245 ms 41684 KB Output is correct
3 Correct 237 ms 41300 KB Output is correct
4 Correct 38 ms 16688 KB Output is correct
5 Correct 1977 ms 41400 KB Output is correct
6 Correct 1155 ms 41016 KB Output is correct
7 Execution timed out 3570 ms 39324 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16716 KB Output is correct
2 Correct 269 ms 47640 KB Output is correct
3 Correct 266 ms 48316 KB Output is correct
4 Correct 213 ms 49408 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16716 KB Output is correct
2 Correct 269 ms 47640 KB Output is correct
3 Correct 266 ms 48316 KB Output is correct
4 Correct 213 ms 49408 KB Output is correct
5 Correct 24 ms 16724 KB Output is correct
6 Correct 1134 ms 47048 KB Output is correct
7 Correct 2923 ms 47512 KB Output is correct
8 Correct 1899 ms 47076 KB Output is correct
9 Correct 1945 ms 47316 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16724 KB Output is correct
2 Correct 177 ms 40516 KB Output is correct
3 Correct 361 ms 40856 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16724 KB Output is correct
2 Correct 177 ms 40516 KB Output is correct
3 Correct 361 ms 40856 KB Output is correct
4 Correct 32 ms 16740 KB Output is correct
5 Correct 1970 ms 40912 KB Output is correct
6 Correct 1343 ms 40700 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16756 KB Output is correct
2 Correct 319 ms 47176 KB Output is correct
3 Correct 351 ms 47480 KB Output is correct
4 Correct 228 ms 49024 KB Output is correct
5 Correct 22 ms 16736 KB Output is correct
6 Correct 174 ms 40668 KB Output is correct
7 Correct 327 ms 40832 KB Output is correct
8 Correct 373 ms 42188 KB Output is correct
9 Correct 363 ms 42184 KB Output is correct
10 Correct 529 ms 43816 KB Output is correct
11 Correct 668 ms 43140 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16756 KB Output is correct
2 Correct 319 ms 47176 KB Output is correct
3 Correct 351 ms 47480 KB Output is correct
4 Correct 228 ms 49024 KB Output is correct
5 Correct 22 ms 16736 KB Output is correct
6 Correct 174 ms 40668 KB Output is correct
7 Correct 327 ms 40832 KB Output is correct
8 Correct 373 ms 42188 KB Output is correct
9 Correct 363 ms 42184 KB Output is correct
10 Correct 529 ms 43816 KB Output is correct
11 Correct 668 ms 43140 KB Output is correct
12 Correct 26 ms 16724 KB Output is correct
13 Correct 1201 ms 47528 KB Output is correct
14 Correct 2970 ms 47520 KB Output is correct
15 Correct 2188 ms 47132 KB Output is correct
16 Correct 2072 ms 47308 KB Output is correct
17 Correct 29 ms 16716 KB Output is correct
18 Correct 1953 ms 40780 KB Output is correct
19 Correct 1255 ms 40700 KB Output is correct
20 Incorrect 1880 ms 41968 KB Extra information in the output file
21 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16724 KB Output is correct
2 Correct 28 ms 17648 KB Output is correct
3 Correct 31 ms 17676 KB Output is correct
4 Correct 28 ms 17644 KB Output is correct
5 Correct 27 ms 17868 KB Output is correct
6 Correct 31 ms 17640 KB Output is correct
7 Correct 24 ms 16768 KB Output is correct
8 Correct 246 ms 40872 KB Output is correct
9 Correct 271 ms 41232 KB Output is correct
10 Correct 22 ms 16692 KB Output is correct
11 Correct 278 ms 47388 KB Output is correct
12 Correct 297 ms 47328 KB Output is correct
13 Correct 223 ms 48960 KB Output is correct
14 Correct 33 ms 16716 KB Output is correct
15 Correct 193 ms 40092 KB Output is correct
16 Correct 302 ms 40172 KB Output is correct
17 Correct 413 ms 41596 KB Output is correct
18 Correct 333 ms 41700 KB Output is correct
19 Correct 740 ms 43188 KB Output is correct
20 Correct 467 ms 42632 KB Output is correct
21 Correct 246 ms 40868 KB Output is correct
22 Correct 349 ms 40868 KB Output is correct
23 Correct 308 ms 41544 KB Output is correct
24 Correct 276 ms 41164 KB Output is correct
25 Correct 352 ms 41060 KB Output is correct
26 Correct 346 ms 39116 KB Output is correct
27 Correct 343 ms 39084 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16724 KB Output is correct
2 Correct 28 ms 17648 KB Output is correct
3 Correct 31 ms 17676 KB Output is correct
4 Correct 28 ms 17644 KB Output is correct
5 Correct 27 ms 17868 KB Output is correct
6 Correct 31 ms 17640 KB Output is correct
7 Correct 24 ms 16768 KB Output is correct
8 Correct 246 ms 40872 KB Output is correct
9 Correct 271 ms 41232 KB Output is correct
10 Correct 22 ms 16692 KB Output is correct
11 Correct 278 ms 47388 KB Output is correct
12 Correct 297 ms 47328 KB Output is correct
13 Correct 223 ms 48960 KB Output is correct
14 Correct 33 ms 16716 KB Output is correct
15 Correct 193 ms 40092 KB Output is correct
16 Correct 302 ms 40172 KB Output is correct
17 Correct 413 ms 41596 KB Output is correct
18 Correct 333 ms 41700 KB Output is correct
19 Correct 740 ms 43188 KB Output is correct
20 Correct 467 ms 42632 KB Output is correct
21 Correct 246 ms 40868 KB Output is correct
22 Correct 349 ms 40868 KB Output is correct
23 Correct 308 ms 41544 KB Output is correct
24 Correct 276 ms 41164 KB Output is correct
25 Correct 352 ms 41060 KB Output is correct
26 Correct 346 ms 39116 KB Output is correct
27 Correct 343 ms 39084 KB Output is correct
28 Correct 40 ms 16016 KB Output is correct
29 Incorrect 595 ms 16600 KB Extra information in the output file
30 Halted 0 ms 0 KB -