oj.uz

답안 #865847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865847 2023-10-24T23:39:58 Z AbdelmagedNour Inside information (BOI21_servers) C++17
82.5 / 100
 3500 ms 53428 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N=250005,SQ=600;
vector<vector<pair<int,int>>>adj(N);
vector<int>cur_adj[N],order;
int in[N],out[N],dep[N],p[N][19],val[N],max_inc[N],max_dec[N],T;
void init_dfs(int v,int par){
	in[v]=++T;order.push_back(v);
	p[v][0]=par;
	for(int i=1;i<18;i++)p[v][i]=p[p[v][i-1]][i-1];
	max_inc[v]=max_dec[v]=par;
	if(val[v]<val[par])max_inc[v]=max_inc[par];
	else max_dec[v]=max_dec[par];
	for(auto e:adj[v]){
		int u=e.first,w=e.second;
		if(u==par)continue;
		dep[u]=dep[v]+1;
		val[u]=w;
		init_dfs(u,v);
	}
	out[v]=T;
}
bool anc(int v,int u){
	return in[v]<=in[u]&&out[u]<=out[v];
}
int max_in_path(int u,int v){
	if(anc(u,v))return val[v];
	int pu=u,pv=v;
	for(int i=17;i>=0;i--){
		if(!anc(p[pu][i],v))pu=p[pu][i];
		if(!anc(p[pv][i],u))pv=p[pv][i];
	}
	if(p[pu][0]==v)return val[pu];
	return val[pu]<val[pv]?val[v]:INT_MAX;
}
bool can_reach(int u,int v,int Time){
	if(u==v)return 1;
	if((!anc(max_inc[u],v))||(!anc(max_dec[v],u)))return 0;
	if(!anc(v,u)&&val[v]>Time)return 0;
	return max_in_path(u,v)<=Time;
}
int dp_down[N],dp_up[N],dp[N],vis[N];
void dfs_down(int v,int par){
	if(vis[v])return;
	vis[v]=1;
	dp_down[v]=dp[v]=1;
	for(auto u:cur_adj[v]){
		if(u==par)continue;
		dfs_down(u,v);
		if(val[u]>val[v])dp_down[v]+=dp_down[u];
		dp[v]+=dp_down[u];
	}
}
void dfs_up(int v,int par,int sum=0){
	dp_up[v]=sum+(par!=v);
	if(val[par]>val[v])dp_up[v]+=dp_up[par];
	dp[v]+=dp_up[v];
	sum=0;
	for(int i=cur_adj[v].size()-1;i>=0;i--){
		int u=cur_adj[v][i];
		if(u==par)continue;
		dfs_up(u,v,sum);
		sum+=dp_down[u];
	}
}
void reclac(){
	memset(vis+1,0,int(order.size())*sizeof(vis[1]));
	for(auto&u:order){
		if(vis[u])continue;
		dfs_down(u,u);
		dfs_up(u,u);
	}
}
char op[N];
int A[N],B[N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<n+q;i++){
		cin>>op[i];
		if(op[i]=='S'){
			cin>>A[i]>>B[i];
			adj[A[i]].push_back({B[i],i});
			adj[B[i]].push_back({A[i],i});
		}
		if(op[i]=='Q')cin>>A[i]>>B[i];
		if(op[i]=='C')cin>>A[i];
	}
	init_dfs(1,1);
	fill(dp+1,dp+n+1,1);
	int cnt=0;
	vector<int>edges;
	for(int i=1;i<n+q;i++){
		if(cnt==SQ)reclac(),cnt=0,edges.clear();
		if(op[i]=='S'){
			edges.push_back(i);
			cur_adj[A[i]].push_back(B[i]);
			cur_adj[B[i]].push_back(A[i]);
			cnt++;
		}else if(op[i]=='Q')cout<<(can_reach(B[i],A[i],i)?"yes\n":"no\n");
		else{
			int res=dp[A[i]];
			for(auto&e:edges){
				int u=A[e],v=B[e];
				if(val[u]!=e)swap(u,v);
				if(!anc(u,A[i])&&can_reach(A[i],u,i))res++;
				else if(anc(u,A[i])&&can_reach(A[i],v,i))res++;
			}
			cout<<res<<"\n";
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 22620 KB Output is correct
2 Correct 24 ms 22876 KB Output is correct
3 Correct 33 ms 23068 KB Output is correct
4 Correct 25 ms 22868 KB Output is correct
5 Correct 24 ms 23132 KB Output is correct
6 Correct 37 ms 22868 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 22620 KB Output is correct
2 Correct 24 ms 22876 KB Output is correct
3 Correct 33 ms 23068 KB Output is correct
4 Correct 25 ms 22868 KB Output is correct
5 Correct 24 ms 23132 KB Output is correct
6 Correct 37 ms 22868 KB Output is correct
7 Correct 29 ms 22616 KB Output is correct
8 Correct 150 ms 22788 KB Output is correct
9 Correct 571 ms 23152 KB Output is correct
10 Correct 175 ms 22928 KB Output is correct
11 Correct 156 ms 23060 KB Output is correct
12 Correct 2410 ms 23320 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 22620 KB Output is correct
2 Correct 495 ms 42036 KB Output is correct
3 Correct 479 ms 41964 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 22620 KB Output is correct
2 Correct 495 ms 42036 KB Output is correct
3 Correct 479 ms 41964 KB Output is correct
4 Correct 57 ms 22612 KB Output is correct
5 Correct 1294 ms 41948 KB Output is correct
6 Correct 819 ms 44228 KB Output is correct
7 Correct 2828 ms 44344 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 22608 KB Output is correct
2 Correct 634 ms 50116 KB Output is correct
3 Correct 643 ms 50400 KB Output is correct
4 Correct 548 ms 51660 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 22608 KB Output is correct
2 Correct 634 ms 50116 KB Output is correct
3 Correct 643 ms 50400 KB Output is correct
4 Correct 548 ms 51660 KB Output is correct
5 Correct 21 ms 22616 KB Output is correct
6 Correct 812 ms 50132 KB Output is correct
7 Correct 1468 ms 50120 KB Output is correct
8 Correct 929 ms 50124 KB Output is correct
9 Correct 928 ms 49908 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22616 KB Output is correct
2 Correct 365 ms 41428 KB Output is correct
3 Correct 696 ms 41820 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22616 KB Output is correct
2 Correct 365 ms 41428 KB Output is correct
3 Correct 696 ms 41820 KB Output is correct
4 Correct 28 ms 22616 KB Output is correct
5 Correct 1765 ms 41928 KB Output is correct
6 Correct 862 ms 41576 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22620 KB Output is correct
2 Correct 643 ms 50044 KB Output is correct
3 Correct 639 ms 49996 KB Output is correct
4 Correct 604 ms 51612 KB Output is correct
5 Correct 19 ms 22616 KB Output is correct
6 Correct 356 ms 41416 KB Output is correct
7 Correct 686 ms 41728 KB Output is correct
8 Correct 726 ms 42676 KB Output is correct
9 Correct 742 ms 42964 KB Output is correct
10 Correct 1310 ms 44956 KB Output is correct
11 Correct 1101 ms 48148 KB Output is correct

Subtask #10
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22620 KB Output is correct
2 Correct 643 ms 50044 KB Output is correct
3 Correct 639 ms 49996 KB Output is correct
4 Correct 604 ms 51612 KB Output is correct
5 Correct 19 ms 22616 KB Output is correct
6 Correct 356 ms 41416 KB Output is correct
7 Correct 686 ms 41728 KB Output is correct
8 Correct 726 ms 42676 KB Output is correct
9 Correct 742 ms 42964 KB Output is correct
10 Correct 1310 ms 44956 KB Output is correct
11 Correct 1101 ms 48148 KB Output is correct
12 Correct 22 ms 23380 KB Output is correct
13 Correct 806 ms 53224 KB Output is correct
14 Correct 1426 ms 53428 KB Output is correct
15 Correct 923 ms 52520 KB Output is correct
16 Correct 934 ms 52936 KB Output is correct
17 Correct 26 ms 23388 KB Output is correct
18 Correct 1755 ms 44728 KB Output is correct
19 Correct 858 ms 44524 KB Output is correct
20 Correct 986 ms 45624 KB Output is correct
21 Correct 923 ms 45780 KB Output is correct
22 Correct 3000 ms 47012 KB Output is correct
23 Correct 2055 ms 49456 KB Output is correct
24 Correct 1508 ms 49388 KB Output is correct

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 22616 KB Output is correct
2 Correct 24 ms 22972 KB Output is correct
3 Correct 34 ms 22948 KB Output is correct
4 Correct 25 ms 22864 KB Output is correct
5 Correct 27 ms 23128 KB Output is correct
6 Correct 37 ms 22944 KB Output is correct
7 Correct 25 ms 22620 KB Output is correct
8 Correct 506 ms 42076 KB Output is correct
9 Correct 464 ms 41924 KB Output is correct
10 Correct 19 ms 22620 KB Output is correct
11 Correct 623 ms 50004 KB Output is correct
12 Correct 632 ms 49844 KB Output is correct
13 Correct 603 ms 51712 KB Output is correct
14 Correct 19 ms 22520 KB Output is correct
15 Correct 364 ms 41492 KB Output is correct
16 Correct 672 ms 41652 KB Output is correct
17 Correct 718 ms 42960 KB Output is correct
18 Correct 743 ms 42788 KB Output is correct
19 Correct 1142 ms 45000 KB Output is correct
20 Correct 1050 ms 48192 KB Output is correct
21 Correct 487 ms 45256 KB Output is correct
22 Correct 500 ms 45596 KB Output is correct
23 Correct 560 ms 45780 KB Output is correct
24 Correct 553 ms 46036 KB Output is correct
25 Correct 697 ms 47180 KB Output is correct
26 Correct 754 ms 45112 KB Output is correct
27 Correct 715 ms 44956 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 22616 KB Output is correct
2 Correct 24 ms 22972 KB Output is correct
3 Correct 34 ms 22948 KB Output is correct
4 Correct 25 ms 22864 KB Output is correct
5 Correct 27 ms 23128 KB Output is correct
6 Correct 37 ms 22944 KB Output is correct
7 Correct 25 ms 22620 KB Output is correct
8 Correct 506 ms 42076 KB Output is correct
9 Correct 464 ms 41924 KB Output is correct
10 Correct 19 ms 22620 KB Output is correct
11 Correct 623 ms 50004 KB Output is correct
12 Correct 632 ms 49844 KB Output is correct
13 Correct 603 ms 51712 KB Output is correct
14 Correct 19 ms 22520 KB Output is correct
15 Correct 364 ms 41492 KB Output is correct
16 Correct 672 ms 41652 KB Output is correct
17 Correct 718 ms 42960 KB Output is correct
18 Correct 743 ms 42788 KB Output is correct
19 Correct 1142 ms 45000 KB Output is correct
20 Correct 1050 ms 48192 KB Output is correct
21 Correct 487 ms 45256 KB Output is correct
22 Correct 500 ms 45596 KB Output is correct
23 Correct 560 ms 45780 KB Output is correct
24 Correct 553 ms 46036 KB Output is correct
25 Correct 697 ms 47180 KB Output is correct
26 Correct 754 ms 45112 KB Output is correct
27 Correct 715 ms 44956 KB Output is correct
28 Correct 29 ms 23376 KB Output is correct
29 Correct 157 ms 24224 KB Output is correct
30 Correct 564 ms 24004 KB Output is correct
31 Correct 171 ms 24144 KB Output is correct
32 Correct 157 ms 24140 KB Output is correct
33 Correct 2414 ms 24720 KB Output is correct
34 Correct 57 ms 23380 KB Output is correct
35 Correct 1287 ms 44772 KB Output is correct
36 Correct 834 ms 43984 KB Output is correct
37 Correct 2833 ms 44236 KB Output is correct
38 Correct 22 ms 23476 KB Output is correct
39 Correct 792 ms 52960 KB Output is correct
40 Correct 1446 ms 53272 KB Output is correct
41 Correct 922 ms 52524 KB Output is correct
42 Correct 925 ms 52560 KB Output is correct
43 Correct 25 ms 23492 KB Output is correct
44 Correct 1757 ms 44588 KB Output is correct
45 Correct 831 ms 44332 KB Output is correct
46 Correct 966 ms 45572 KB Output is correct
47 Correct 920 ms 45940 KB Output is correct
48 Correct 3032 ms 47344 KB Output is correct
49 Correct 2047 ms 49356 KB Output is correct
50 Correct 1377 ms 49452 KB Output is correct
51 Correct 1824 ms 45752 KB Output is correct
52 Execution timed out 3537 ms 45068 KB Time limit exceeded
53 Halted 0 ms 0 KB -