oj.uz

Submission #817860

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

using namespace std ;

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

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 15820 KB Output is correct
2 Correct 27 ms 16592 KB Output is correct
3 Correct 29 ms 16704 KB Output is correct
4 Correct 27 ms 16744 KB Output is correct
5 Correct 26 ms 16900 KB Output is correct
6 Correct 30 ms 16716 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15820 KB Output is correct
2 Correct 27 ms 16592 KB Output is correct
3 Correct 29 ms 16704 KB Output is correct
4 Correct 27 ms 16744 KB Output is correct
5 Correct 26 ms 16900 KB Output is correct
6 Correct 30 ms 16716 KB Output is correct
7 Correct 30 ms 15808 KB Output is correct
8 Incorrect 1018 ms 16512 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 23 ms 15828 KB Output is correct
2 Correct 179 ms 39076 KB Output is correct
3 Correct 179 ms 39056 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15828 KB Output is correct
2 Correct 179 ms 39076 KB Output is correct
3 Correct 179 ms 39056 KB Output is correct
4 Correct 38 ms 15876 KB Output is correct
5 Correct 3248 ms 39080 KB Output is correct
6 Correct 2170 ms 39372 KB Output is correct
7 Execution timed out 3577 ms 36128 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 202 ms 45228 KB Output is correct
3 Correct 193 ms 45156 KB Output is correct
4 Correct 172 ms 46776 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 202 ms 45228 KB Output is correct
3 Correct 193 ms 45156 KB Output is correct
4 Correct 172 ms 46776 KB Output is correct
5 Correct 24 ms 15864 KB Output is correct
6 Correct 1898 ms 45128 KB Output is correct
7 Execution timed out 3585 ms 44108 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 150 ms 38548 KB Output is correct
3 Correct 219 ms 38688 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 150 ms 38548 KB Output is correct
3 Correct 219 ms 38688 KB Output is correct
4 Correct 27 ms 15904 KB Output is correct
5 Correct 1644 ms 38536 KB Output is correct
6 Correct 1890 ms 38592 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15872 KB Output is correct
2 Correct 199 ms 45148 KB Output is correct
3 Correct 191 ms 45220 KB Output is correct
4 Correct 162 ms 46796 KB Output is correct
5 Correct 22 ms 15816 KB Output is correct
6 Correct 143 ms 38552 KB Output is correct
7 Correct 229 ms 38680 KB Output is correct
8 Correct 245 ms 39820 KB Output is correct
9 Correct 258 ms 39976 KB Output is correct
10 Correct 315 ms 41324 KB Output is correct
11 Correct 331 ms 40856 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15872 KB Output is correct
2 Correct 199 ms 45148 KB Output is correct
3 Correct 191 ms 45220 KB Output is correct
4 Correct 162 ms 46796 KB Output is correct
5 Correct 22 ms 15816 KB Output is correct
6 Correct 143 ms 38552 KB Output is correct
7 Correct 229 ms 38680 KB Output is correct
8 Correct 245 ms 39820 KB Output is correct
9 Correct 258 ms 39976 KB Output is correct
10 Correct 315 ms 41324 KB Output is correct
11 Correct 331 ms 40856 KB Output is correct
12 Correct 23 ms 15888 KB Output is correct
13 Correct 1910 ms 45124 KB Output is correct
14 Execution timed out 3567 ms 44088 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15824 KB Output is correct
2 Correct 27 ms 16604 KB Output is correct
3 Correct 29 ms 16736 KB Output is correct
4 Correct 27 ms 16672 KB Output is correct
5 Correct 27 ms 16844 KB Output is correct
6 Correct 30 ms 16724 KB Output is correct
7 Correct 24 ms 15864 KB Output is correct
8 Correct 200 ms 39060 KB Output is correct
9 Correct 173 ms 39060 KB Output is correct
10 Correct 21 ms 15808 KB Output is correct
11 Correct 187 ms 45200 KB Output is correct
12 Correct 193 ms 45148 KB Output is correct
13 Correct 167 ms 46840 KB Output is correct
14 Correct 22 ms 15856 KB Output is correct
15 Correct 144 ms 38536 KB Output is correct
16 Correct 237 ms 38696 KB Output is correct
17 Correct 261 ms 39824 KB Output is correct
18 Correct 236 ms 39912 KB Output is correct
19 Correct 331 ms 41348 KB Output is correct
20 Correct 409 ms 40908 KB Output is correct
21 Correct 276 ms 39180 KB Output is correct
22 Correct 227 ms 39048 KB Output is correct
23 Correct 197 ms 39700 KB Output is correct
24 Correct 220 ms 39784 KB Output is correct
25 Correct 271 ms 40484 KB Output is correct
26 Correct 264 ms 38608 KB Output is correct
27 Correct 218 ms 38604 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15824 KB Output is correct
2 Correct 27 ms 16604 KB Output is correct
3 Correct 29 ms 16736 KB Output is correct
4 Correct 27 ms 16672 KB Output is correct
5 Correct 27 ms 16844 KB Output is correct
6 Correct 30 ms 16724 KB Output is correct
7 Correct 24 ms 15864 KB Output is correct
8 Correct 200 ms 39060 KB Output is correct
9 Correct 173 ms 39060 KB Output is correct
10 Correct 21 ms 15808 KB Output is correct
11 Correct 187 ms 45200 KB Output is correct
12 Correct 193 ms 45148 KB Output is correct
13 Correct 167 ms 46840 KB Output is correct
14 Correct 22 ms 15856 KB Output is correct
15 Correct 144 ms 38536 KB Output is correct
16 Correct 237 ms 38696 KB Output is correct
17 Correct 261 ms 39824 KB Output is correct
18 Correct 236 ms 39912 KB Output is correct
19 Correct 331 ms 41348 KB Output is correct
20 Correct 409 ms 40908 KB Output is correct
21 Correct 276 ms 39180 KB Output is correct
22 Correct 227 ms 39048 KB Output is correct
23 Correct 197 ms 39700 KB Output is correct
24 Correct 220 ms 39784 KB Output is correct
25 Correct 271 ms 40484 KB Output is correct
26 Correct 264 ms 38608 KB Output is correct
27 Correct 218 ms 38604 KB Output is correct
28 Correct 30 ms 15888 KB Output is correct
29 Incorrect 995 ms 16560 KB Extra information in the output file
30 Halted 0 ms 0 KB -