oj.uz

Submission #817857

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

using namespace std ;

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

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 15872 KB Output is correct
2 Correct 26 ms 16568 KB Output is correct
3 Correct 29 ms 16768 KB Output is correct
4 Correct 29 ms 16716 KB Output is correct
5 Correct 26 ms 16852 KB Output is correct
6 Correct 41 ms 16684 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15872 KB Output is correct
2 Correct 26 ms 16568 KB Output is correct
3 Correct 29 ms 16768 KB Output is correct
4 Correct 29 ms 16716 KB Output is correct
5 Correct 26 ms 16852 KB Output is correct
6 Correct 41 ms 16684 KB Output is correct
7 Correct 31 ms 15800 KB Output is correct
8 Incorrect 793 ms 16564 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 15828 KB Output is correct
2 Correct 241 ms 39036 KB Output is correct
3 Correct 246 ms 38984 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15828 KB Output is correct
2 Correct 241 ms 39036 KB Output is correct
3 Correct 246 ms 38984 KB Output is correct
4 Correct 38 ms 15848 KB Output is correct
5 Correct 3030 ms 39108 KB Output is correct
6 Correct 1951 ms 39316 KB Output is correct
7 Execution timed out 3573 ms 36196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15900 KB Output is correct
2 Correct 260 ms 45196 KB Output is correct
3 Correct 267 ms 45144 KB Output is correct
4 Correct 187 ms 46680 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15900 KB Output is correct
2 Correct 260 ms 45196 KB Output is correct
3 Correct 267 ms 45144 KB Output is correct
4 Correct 187 ms 46680 KB Output is correct
5 Correct 27 ms 15812 KB Output is correct
6 Correct 1739 ms 45120 KB Output is correct
7 Execution timed out 3542 ms 44324 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 147 ms 38516 KB Output is correct
3 Correct 264 ms 38804 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 147 ms 38516 KB Output is correct
3 Correct 264 ms 38804 KB Output is correct
4 Correct 27 ms 15828 KB Output is correct
5 Correct 3039 ms 38616 KB Output is correct
6 Correct 1850 ms 38600 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 206 ms 45212 KB Output is correct
3 Correct 265 ms 45120 KB Output is correct
4 Correct 194 ms 46660 KB Output is correct
5 Correct 22 ms 15840 KB Output is correct
6 Correct 137 ms 38520 KB Output is correct
7 Correct 331 ms 38584 KB Output is correct
8 Correct 327 ms 39920 KB Output is correct
9 Correct 272 ms 39980 KB Output is correct
10 Correct 434 ms 41420 KB Output is correct
11 Correct 587 ms 40860 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 206 ms 45212 KB Output is correct
3 Correct 265 ms 45120 KB Output is correct
4 Correct 194 ms 46660 KB Output is correct
5 Correct 22 ms 15840 KB Output is correct
6 Correct 137 ms 38520 KB Output is correct
7 Correct 331 ms 38584 KB Output is correct
8 Correct 327 ms 39920 KB Output is correct
9 Correct 272 ms 39980 KB Output is correct
10 Correct 434 ms 41420 KB Output is correct
11 Correct 587 ms 40860 KB Output is correct
12 Correct 24 ms 15832 KB Output is correct
13 Correct 1785 ms 45128 KB Output is correct
14 Execution timed out 3570 ms 44324 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 26 ms 16660 KB Output is correct
3 Correct 30 ms 16724 KB Output is correct
4 Correct 27 ms 16660 KB Output is correct
5 Correct 27 ms 16880 KB Output is correct
6 Correct 30 ms 16716 KB Output is correct
7 Correct 23 ms 15884 KB Output is correct
8 Correct 188 ms 39020 KB Output is correct
9 Correct 195 ms 39100 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 226 ms 45268 KB Output is correct
12 Correct 204 ms 45132 KB Output is correct
13 Correct 163 ms 46660 KB Output is correct
14 Correct 22 ms 15864 KB Output is correct
15 Correct 148 ms 38732 KB Output is correct
16 Correct 235 ms 38656 KB Output is correct
17 Correct 254 ms 39884 KB Output is correct
18 Correct 289 ms 39972 KB Output is correct
19 Correct 352 ms 41328 KB Output is correct
20 Correct 386 ms 40824 KB Output is correct
21 Correct 194 ms 39100 KB Output is correct
22 Correct 199 ms 39032 KB Output is correct
23 Correct 233 ms 39744 KB Output is correct
24 Correct 219 ms 39816 KB Output is correct
25 Correct 267 ms 40472 KB Output is correct
26 Correct 273 ms 38480 KB Output is correct
27 Correct 247 ms 38584 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15820 KB Output is correct
2 Correct 26 ms 16660 KB Output is correct
3 Correct 30 ms 16724 KB Output is correct
4 Correct 27 ms 16660 KB Output is correct
5 Correct 27 ms 16880 KB Output is correct
6 Correct 30 ms 16716 KB Output is correct
7 Correct 23 ms 15884 KB Output is correct
8 Correct 188 ms 39020 KB Output is correct
9 Correct 195 ms 39100 KB Output is correct
10 Correct 21 ms 15828 KB Output is correct
11 Correct 226 ms 45268 KB Output is correct
12 Correct 204 ms 45132 KB Output is correct
13 Correct 163 ms 46660 KB Output is correct
14 Correct 22 ms 15864 KB Output is correct
15 Correct 148 ms 38732 KB Output is correct
16 Correct 235 ms 38656 KB Output is correct
17 Correct 254 ms 39884 KB Output is correct
18 Correct 289 ms 39972 KB Output is correct
19 Correct 352 ms 41328 KB Output is correct
20 Correct 386 ms 40824 KB Output is correct
21 Correct 194 ms 39100 KB Output is correct
22 Correct 199 ms 39032 KB Output is correct
23 Correct 233 ms 39744 KB Output is correct
24 Correct 219 ms 39816 KB Output is correct
25 Correct 267 ms 40472 KB Output is correct
26 Correct 273 ms 38480 KB Output is correct
27 Correct 247 ms 38584 KB Output is correct
28 Correct 30 ms 15848 KB Output is correct
29 Incorrect 768 ms 16548 KB Extra information in the output file
30 Halted 0 ms 0 KB -