oj.uz

Submission #865853

# Submission time Handle Problem Language Result Execution time Memory
865853 2023-10-24T23:50:35 Z AbdelmagedNour Inside information (BOI21_servers) C++17
82.5 / 100
 3500 ms 52340 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
const int N=250005,SQ=450;
vector<vector<pair<int,int>>>adj(N);
vector<int>cur_adj[N],order;
int in[N],out[N],dep[N],p[N][18],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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23644 KB Output is correct
2 Correct 24 ms 23892 KB Output is correct
3 Correct 36 ms 24140 KB Output is correct
4 Correct 25 ms 23900 KB Output is correct
5 Correct 24 ms 24148 KB Output is correct
6 Correct 36 ms 23924 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23644 KB Output is correct
2 Correct 24 ms 23892 KB Output is correct
3 Correct 36 ms 24140 KB Output is correct
4 Correct 25 ms 23900 KB Output is correct
5 Correct 24 ms 24148 KB Output is correct
6 Correct 36 ms 23924 KB Output is correct
7 Correct 28 ms 23640 KB Output is correct
8 Correct 123 ms 23896 KB Output is correct
9 Correct 448 ms 23964 KB Output is correct
10 Correct 134 ms 23892 KB Output is correct
11 Correct 163 ms 24660 KB Output is correct
12 Correct 2149 ms 24688 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23588 KB Output is correct
2 Correct 589 ms 42944 KB Output is correct
3 Correct 610 ms 42492 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23588 KB Output is correct
2 Correct 589 ms 42944 KB Output is correct
3 Correct 610 ms 42492 KB Output is correct
4 Correct 54 ms 23644 KB Output is correct
5 Correct 1186 ms 42804 KB Output is correct
6 Correct 857 ms 43072 KB Output is correct
7 Correct 2272 ms 42744 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23644 KB Output is correct
2 Correct 825 ms 50912 KB Output is correct
3 Correct 813 ms 50808 KB Output is correct
4 Correct 712 ms 52168 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23644 KB Output is correct
2 Correct 825 ms 50912 KB Output is correct
3 Correct 813 ms 50808 KB Output is correct
4 Correct 712 ms 52168 KB Output is correct
5 Correct 21 ms 23644 KB Output is correct
6 Correct 951 ms 50892 KB Output is correct
7 Correct 1331 ms 50888 KB Output is correct
8 Correct 1025 ms 50360 KB Output is correct
9 Correct 1022 ms 50820 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23644 KB Output is correct
2 Correct 448 ms 41932 KB Output is correct
3 Correct 828 ms 42060 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23644 KB Output is correct
2 Correct 448 ms 41932 KB Output is correct
3 Correct 828 ms 42060 KB Output is correct
4 Correct 26 ms 23644 KB Output is correct
5 Correct 1167 ms 42088 KB Output is correct
6 Correct 979 ms 41944 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23640 KB Output is correct
2 Correct 825 ms 50480 KB Output is correct
3 Correct 810 ms 50488 KB Output is correct
4 Correct 688 ms 52340 KB Output is correct
5 Correct 19 ms 23560 KB Output is correct
6 Correct 459 ms 42116 KB Output is correct
7 Correct 861 ms 42112 KB Output is correct
8 Correct 914 ms 43336 KB Output is correct
9 Correct 933 ms 43416 KB Output is correct
10 Correct 1359 ms 45524 KB Output is correct
11 Correct 1413 ms 45380 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23640 KB Output is correct
2 Correct 825 ms 50480 KB Output is correct
3 Correct 810 ms 50488 KB Output is correct
4 Correct 688 ms 52340 KB Output is correct
5 Correct 19 ms 23560 KB Output is correct
6 Correct 459 ms 42116 KB Output is correct
7 Correct 861 ms 42112 KB Output is correct
8 Correct 914 ms 43336 KB Output is correct
9 Correct 933 ms 43416 KB Output is correct
10 Correct 1359 ms 45524 KB Output is correct
11 Correct 1413 ms 45380 KB Output is correct
12 Correct 21 ms 23640 KB Output is correct
13 Correct 961 ms 50532 KB Output is correct
14 Correct 1342 ms 50816 KB Output is correct
15 Correct 1027 ms 50380 KB Output is correct
16 Correct 1026 ms 50576 KB Output is correct
17 Correct 24 ms 23640 KB Output is correct
18 Correct 1165 ms 41928 KB Output is correct
19 Correct 989 ms 42012 KB Output is correct
20 Correct 1022 ms 43192 KB Output is correct
21 Correct 1047 ms 43440 KB Output is correct
22 Correct 2826 ms 44716 KB Output is correct
23 Correct 2118 ms 49324 KB Output is correct
24 Correct 1717 ms 49388 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23588 KB Output is correct
2 Correct 24 ms 23896 KB Output is correct
3 Correct 38 ms 24400 KB Output is correct
4 Correct 24 ms 24144 KB Output is correct
5 Correct 23 ms 24156 KB Output is correct
6 Correct 35 ms 24000 KB Output is correct
7 Correct 25 ms 23644 KB Output is correct
8 Correct 611 ms 43028 KB Output is correct
9 Correct 616 ms 42724 KB Output is correct
10 Correct 18 ms 23640 KB Output is correct
11 Correct 818 ms 50668 KB Output is correct
12 Correct 824 ms 50888 KB Output is correct
13 Correct 779 ms 52172 KB Output is correct
14 Correct 19 ms 23640 KB Output is correct
15 Correct 453 ms 42052 KB Output is correct
16 Correct 854 ms 42136 KB Output is correct
17 Correct 910 ms 43216 KB Output is correct
18 Correct 920 ms 43472 KB Output is correct
19 Correct 1348 ms 45768 KB Output is correct
20 Correct 1411 ms 45516 KB Output is correct
21 Correct 606 ms 42440 KB Output is correct
22 Correct 642 ms 42652 KB Output is correct
23 Correct 644 ms 43548 KB Output is correct
24 Correct 710 ms 43476 KB Output is correct
25 Correct 915 ms 44740 KB Output is correct
26 Correct 984 ms 42200 KB Output is correct
27 Correct 906 ms 42000 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23588 KB Output is correct
2 Correct 24 ms 23896 KB Output is correct
3 Correct 38 ms 24400 KB Output is correct
4 Correct 24 ms 24144 KB Output is correct
5 Correct 23 ms 24156 KB Output is correct
6 Correct 35 ms 24000 KB Output is correct
7 Correct 25 ms 23644 KB Output is correct
8 Correct 611 ms 43028 KB Output is correct
9 Correct 616 ms 42724 KB Output is correct
10 Correct 18 ms 23640 KB Output is correct
11 Correct 818 ms 50668 KB Output is correct
12 Correct 824 ms 50888 KB Output is correct
13 Correct 779 ms 52172 KB Output is correct
14 Correct 19 ms 23640 KB Output is correct
15 Correct 453 ms 42052 KB Output is correct
16 Correct 854 ms 42136 KB Output is correct
17 Correct 910 ms 43216 KB Output is correct
18 Correct 920 ms 43472 KB Output is correct
19 Correct 1348 ms 45768 KB Output is correct
20 Correct 1411 ms 45516 KB Output is correct
21 Correct 606 ms 42440 KB Output is correct
22 Correct 642 ms 42652 KB Output is correct
23 Correct 644 ms 43548 KB Output is correct
24 Correct 710 ms 43476 KB Output is correct
25 Correct 915 ms 44740 KB Output is correct
26 Correct 984 ms 42200 KB Output is correct
27 Correct 906 ms 42000 KB Output is correct
28 Correct 29 ms 23644 KB Output is correct
29 Correct 122 ms 23860 KB Output is correct
30 Correct 457 ms 23952 KB Output is correct
31 Correct 132 ms 23936 KB Output is correct
32 Correct 160 ms 24316 KB Output is correct
33 Correct 2141 ms 24336 KB Output is correct
34 Correct 54 ms 23720 KB Output is correct
35 Correct 1230 ms 42516 KB Output is correct
36 Correct 862 ms 42816 KB Output is correct
37 Correct 2302 ms 43060 KB Output is correct
38 Correct 23 ms 23704 KB Output is correct
39 Correct 1079 ms 50316 KB Output is correct
40 Correct 1529 ms 50816 KB Output is correct
41 Correct 1175 ms 52004 KB Output is correct
42 Correct 1158 ms 52092 KB Output is correct
43 Correct 24 ms 24468 KB Output is correct
44 Correct 1183 ms 44148 KB Output is correct
45 Correct 1079 ms 43884 KB Output is correct
46 Correct 1782 ms 45200 KB Output is correct
47 Correct 1731 ms 45360 KB Output is correct
48 Execution timed out 3541 ms 46152 KB Time limit exceeded
49 Halted 0 ms 0 KB -