oj.uz

답안 #817867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817867 2023-08-09T18:21:07 Z MohamedAhmed04 Inside information (BOI21_servers) C++14
7.5 / 100
 3500 ms 45764 KB 
#include <bits/stdc++.h>

using namespace std ;

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

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 ;

vector<int>order ;

void dfs(int node , int par)
{
	in[node] = ++tim , order.push_back(node) ;
	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(auto &node : order)
	{
		if(vis[node])
			continue ;
		dfs2(node , node) ;
		dfs3(node , node , 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 22 ms 15828 KB Output is correct
2 Correct 30 ms 16592 KB Output is correct
3 Correct 31 ms 16736 KB Output is correct
4 Correct 39 ms 16668 KB Output is correct
5 Correct 30 ms 16768 KB Output is correct
6 Correct 34 ms 16812 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Correct 30 ms 16592 KB Output is correct
3 Correct 31 ms 16736 KB Output is correct
4 Correct 39 ms 16668 KB Output is correct
5 Correct 30 ms 16768 KB Output is correct
6 Correct 34 ms 16812 KB Output is correct
7 Correct 31 ms 15832 KB Output is correct
8 Correct 50 ms 16560 KB Output is correct
9 Correct 78 ms 16800 KB Output is correct
10 Correct 51 ms 16656 KB Output is correct
11 Correct 67 ms 16720 KB Output is correct
12 Correct 230 ms 16804 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 15872 KB Output is correct
2 Correct 3297 ms 39524 KB Output is correct
3 Correct 3287 ms 39488 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 15872 KB Output is correct
2 Correct 3297 ms 39524 KB Output is correct
3 Correct 3287 ms 39488 KB Output is correct
4 Correct 40 ms 15932 KB Output is correct
5 Correct 3244 ms 39572 KB Output is correct
6 Execution timed out 3539 ms 39812 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 15820 KB Output is correct
2 Execution timed out 3562 ms 45708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 15820 KB Output is correct
2 Execution timed out 3562 ms 45708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 15796 KB Output is correct
2 Correct 2216 ms 39056 KB Output is correct
3 Execution timed out 3572 ms 38620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 15796 KB Output is correct
2 Correct 2216 ms 39056 KB Output is correct
3 Execution timed out 3572 ms 38620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Execution timed out 3570 ms 45764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Execution timed out 3570 ms 45764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 15840 KB Output is correct
2 Correct 31 ms 16544 KB Output is correct
3 Correct 33 ms 16692 KB Output is correct
4 Correct 34 ms 16716 KB Output is correct
5 Correct 38 ms 16880 KB Output is correct
6 Correct 37 ms 16736 KB Output is correct
7 Correct 25 ms 15860 KB Output is correct
8 Execution timed out 3572 ms 38832 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 15840 KB Output is correct
2 Correct 31 ms 16544 KB Output is correct
3 Correct 33 ms 16692 KB Output is correct
4 Correct 34 ms 16716 KB Output is correct
5 Correct 38 ms 16880 KB Output is correct
6 Correct 37 ms 16736 KB Output is correct
7 Correct 25 ms 15860 KB Output is correct
8 Execution timed out 3572 ms 38832 KB Time limit exceeded
9 Halted 0 ms 0 KB -