oj.uz

답안 #817849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817849 2023-08-09T18:03:17 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
67.5 / 100
 2689 ms 48668 KB 
#include <bits/stdc++.h>

using namespace std ;

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16288 KB Output is correct
2 Correct 28 ms 17360 KB Output is correct
3 Correct 31 ms 17508 KB Output is correct
4 Correct 35 ms 17500 KB Output is correct
5 Correct 27 ms 17612 KB Output is correct
6 Correct 33 ms 17496 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16288 KB Output is correct
2 Correct 28 ms 17360 KB Output is correct
3 Correct 31 ms 17508 KB Output is correct
4 Correct 35 ms 17500 KB Output is correct
5 Correct 27 ms 17612 KB Output is correct
6 Correct 33 ms 17496 KB Output is correct
7 Correct 30 ms 16468 KB Output is correct
8 Incorrect 316 ms 16980 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16200 KB Output is correct
2 Correct 395 ms 39892 KB Output is correct
3 Correct 342 ms 39872 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16200 KB Output is correct
2 Correct 395 ms 39892 KB Output is correct
3 Correct 342 ms 39872 KB Output is correct
4 Correct 39 ms 16332 KB Output is correct
5 Correct 1359 ms 39764 KB Output is correct
6 Correct 739 ms 40112 KB Output is correct
7 Correct 2689 ms 39868 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16200 KB Output is correct
2 Correct 459 ms 45872 KB Output is correct
3 Correct 488 ms 46340 KB Output is correct
4 Correct 399 ms 48388 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16200 KB Output is correct
2 Correct 459 ms 45872 KB Output is correct
3 Correct 488 ms 46340 KB Output is correct
4 Correct 399 ms 48388 KB Output is correct
5 Correct 27 ms 16724 KB Output is correct
6 Correct 953 ms 47016 KB Output is correct
7 Correct 1792 ms 46800 KB Output is correct
8 Correct 1336 ms 47740 KB Output is correct
9 Correct 1272 ms 47668 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 16492 KB Output is correct
2 Correct 272 ms 39836 KB Output is correct
3 Correct 584 ms 40060 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 16492 KB Output is correct
2 Correct 272 ms 39836 KB Output is correct
3 Correct 584 ms 40060 KB Output is correct
4 Correct 31 ms 16424 KB Output is correct
5 Correct 1248 ms 39888 KB Output is correct
6 Correct 857 ms 41536 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16544 KB Output is correct
2 Correct 426 ms 46528 KB Output is correct
3 Correct 452 ms 47020 KB Output is correct
4 Correct 363 ms 48668 KB Output is correct
5 Correct 23 ms 16612 KB Output is correct
6 Correct 255 ms 39956 KB Output is correct
7 Correct 520 ms 40016 KB Output is correct
8 Correct 632 ms 41128 KB Output is correct
9 Correct 676 ms 41272 KB Output is correct
10 Correct 999 ms 42752 KB Output is correct
11 Correct 869 ms 42176 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16544 KB Output is correct
2 Correct 426 ms 46528 KB Output is correct
3 Correct 452 ms 47020 KB Output is correct
4 Correct 363 ms 48668 KB Output is correct
5 Correct 23 ms 16612 KB Output is correct
6 Correct 255 ms 39956 KB Output is correct
7 Correct 520 ms 40016 KB Output is correct
8 Correct 632 ms 41128 KB Output is correct
9 Correct 676 ms 41272 KB Output is correct
10 Correct 999 ms 42752 KB Output is correct
11 Correct 869 ms 42176 KB Output is correct
12 Correct 24 ms 16460 KB Output is correct
13 Correct 900 ms 46400 KB Output is correct
14 Correct 1892 ms 46796 KB Output is correct
15 Correct 1090 ms 47672 KB Output is correct
16 Correct 1207 ms 47616 KB Output is correct
17 Correct 39 ms 16672 KB Output is correct
18 Correct 1222 ms 41600 KB Output is correct
19 Correct 937 ms 41456 KB Output is correct
20 Incorrect 1326 ms 42764 KB Extra information in the output file
21 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 16456 KB Output is correct
2 Correct 27 ms 17892 KB Output is correct
3 Correct 32 ms 17968 KB Output is correct
4 Correct 28 ms 17976 KB Output is correct
5 Correct 38 ms 18128 KB Output is correct
6 Correct 31 ms 17996 KB Output is correct
7 Correct 24 ms 16716 KB Output is correct
8 Correct 358 ms 40332 KB Output is correct
9 Correct 394 ms 40512 KB Output is correct
10 Correct 22 ms 16460 KB Output is correct
11 Correct 427 ms 46696 KB Output is correct
12 Correct 497 ms 46620 KB Output is correct
13 Correct 346 ms 48204 KB Output is correct
14 Correct 22 ms 16464 KB Output is correct
15 Correct 262 ms 40140 KB Output is correct
16 Correct 582 ms 40328 KB Output is correct
17 Correct 660 ms 41428 KB Output is correct
18 Correct 1059 ms 41396 KB Output is correct
19 Correct 1076 ms 42940 KB Output is correct
20 Correct 1894 ms 42344 KB Output is correct
21 Correct 485 ms 40612 KB Output is correct
22 Correct 436 ms 40528 KB Output is correct
23 Correct 581 ms 41276 KB Output is correct
24 Correct 527 ms 41288 KB Output is correct
25 Correct 653 ms 42740 KB Output is correct
26 Correct 671 ms 40828 KB Output is correct
27 Correct 664 ms 40800 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 16456 KB Output is correct
2 Correct 27 ms 17892 KB Output is correct
3 Correct 32 ms 17968 KB Output is correct
4 Correct 28 ms 17976 KB Output is correct
5 Correct 38 ms 18128 KB Output is correct
6 Correct 31 ms 17996 KB Output is correct
7 Correct 24 ms 16716 KB Output is correct
8 Correct 358 ms 40332 KB Output is correct
9 Correct 394 ms 40512 KB Output is correct
10 Correct 22 ms 16460 KB Output is correct
11 Correct 427 ms 46696 KB Output is correct
12 Correct 497 ms 46620 KB Output is correct
13 Correct 346 ms 48204 KB Output is correct
14 Correct 22 ms 16464 KB Output is correct
15 Correct 262 ms 40140 KB Output is correct
16 Correct 582 ms 40328 KB Output is correct
17 Correct 660 ms 41428 KB Output is correct
18 Correct 1059 ms 41396 KB Output is correct
19 Correct 1076 ms 42940 KB Output is correct
20 Correct 1894 ms 42344 KB Output is correct
21 Correct 485 ms 40612 KB Output is correct
22 Correct 436 ms 40528 KB Output is correct
23 Correct 581 ms 41276 KB Output is correct
24 Correct 527 ms 41288 KB Output is correct
25 Correct 653 ms 42740 KB Output is correct
26 Correct 671 ms 40828 KB Output is correct
27 Correct 664 ms 40800 KB Output is correct
28 Correct 31 ms 16716 KB Output is correct
29 Incorrect 352 ms 17688 KB Extra information in the output file
30 Halted 0 ms 0 KB -