oj.uz

Submission #865842

# Submission time Handle Problem Language Result Execution time Memory
865842 2023-10-24T23:27:25 Z AbdelmagedNour Inside information (BOI21_servers) C++17
27.5 / 100
 3500 ms 275632 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=250005,SQ=600;
vector<vector<pair<int,int>>>adj(N);
deque<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<19;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=18;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){
	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(auto u:cur_adj[v]){
		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);
	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_front(B[i]);
			cur_adj[B[i]].push_front(A[i]);
			cnt++;
		}else if(op[i]=='Q')cout<<(can_reach(B[i],A[i],i)?"yes\n":"no\n");
		else{
			int res=max(dp[A[i]],1);
			for(auto e:edges){
				int u=A[e],v=B[e];
				if(val[u]!=e)swap(u,v);
				if(can_reach(A[i],u,i)&&!anc(u,A[i]))res++;
				else if(can_reach(A[i],v,i)&&anc(u,A[i]))res++;
			}
			cout<<res<<"\n";
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 178540 KB Output is correct
2 Correct 128 ms 181236 KB Output is correct
3 Correct 148 ms 181468 KB Output is correct
4 Correct 134 ms 188348 KB Output is correct
5 Correct 119 ms 188240 KB Output is correct
6 Correct 134 ms 188760 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 178540 KB Output is correct
2 Correct 128 ms 181236 KB Output is correct
3 Correct 148 ms 181468 KB Output is correct
4 Correct 134 ms 188348 KB Output is correct
5 Correct 119 ms 188240 KB Output is correct
6 Correct 134 ms 188760 KB Output is correct
7 Correct 138 ms 179784 KB Output is correct
8 Correct 265 ms 186200 KB Output is correct
9 Correct 841 ms 188544 KB Output is correct
10 Correct 281 ms 186504 KB Output is correct
11 Correct 286 ms 186456 KB Output is correct
12 Correct 2887 ms 186600 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 115 ms 183948 KB Output is correct
2 Correct 3055 ms 264528 KB Output is correct
3 Correct 2981 ms 265664 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 115 ms 183948 KB Output is correct
2 Correct 3055 ms 264528 KB Output is correct
3 Correct 2981 ms 265664 KB Output is correct
4 Correct 170 ms 183892 KB Output is correct
5 Execution timed out 3602 ms 256408 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 183880 KB Output is correct
2 Correct 2944 ms 272212 KB Output is correct
3 Correct 2956 ms 272404 KB Output is correct
4 Correct 1320 ms 275452 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 183880 KB Output is correct
2 Correct 2944 ms 272212 KB Output is correct
3 Correct 2956 ms 272404 KB Output is correct
4 Correct 1320 ms 275452 KB Output is correct
5 Correct 114 ms 183888 KB Output is correct
6 Correct 3093 ms 271064 KB Output is correct
7 Correct 3113 ms 272928 KB Output is correct
8 Correct 3179 ms 270336 KB Output is correct
9 Correct 3269 ms 270512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 184144 KB Output is correct
2 Correct 2417 ms 265428 KB Output is correct
3 Correct 2799 ms 266076 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 184144 KB Output is correct
2 Correct 2417 ms 265428 KB Output is correct
3 Correct 2799 ms 266076 KB Output is correct
4 Correct 120 ms 183892 KB Output is correct
5 Execution timed out 3532 ms 264116 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 183720 KB Output is correct
2 Correct 2912 ms 272520 KB Output is correct
3 Correct 2941 ms 272516 KB Output is correct
4 Correct 1387 ms 275596 KB Output is correct
5 Correct 111 ms 183888 KB Output is correct
6 Correct 2449 ms 265824 KB Output is correct
7 Correct 2819 ms 266180 KB Output is correct
8 Correct 3177 ms 266324 KB Output is correct
9 Correct 3124 ms 266492 KB Output is correct
10 Execution timed out 3613 ms 270364 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 183720 KB Output is correct
2 Correct 2912 ms 272520 KB Output is correct
3 Correct 2941 ms 272516 KB Output is correct
4 Correct 1387 ms 275596 KB Output is correct
5 Correct 111 ms 183888 KB Output is correct
6 Correct 2449 ms 265824 KB Output is correct
7 Correct 2819 ms 266180 KB Output is correct
8 Correct 3177 ms 266324 KB Output is correct
9 Correct 3124 ms 266492 KB Output is correct
10 Execution timed out 3613 ms 270364 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 183808 KB Output is correct
2 Correct 125 ms 188500 KB Output is correct
3 Correct 130 ms 188752 KB Output is correct
4 Correct 126 ms 188932 KB Output is correct
5 Correct 119 ms 188756 KB Output is correct
6 Correct 136 ms 188816 KB Output is correct
7 Correct 122 ms 183892 KB Output is correct
8 Correct 3073 ms 264392 KB Output is correct
9 Correct 2996 ms 265620 KB Output is correct
10 Correct 109 ms 183888 KB Output is correct
11 Correct 2887 ms 272560 KB Output is correct
12 Correct 2924 ms 272020 KB Output is correct
13 Correct 1341 ms 275632 KB Output is correct
14 Correct 116 ms 183892 KB Output is correct
15 Correct 2464 ms 265412 KB Output is correct
16 Correct 2847 ms 266208 KB Output is correct
17 Correct 2992 ms 266252 KB Output is correct
18 Correct 3053 ms 266500 KB Output is correct
19 Execution timed out 3564 ms 270328 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 183808 KB Output is correct
2 Correct 125 ms 188500 KB Output is correct
3 Correct 130 ms 188752 KB Output is correct
4 Correct 126 ms 188932 KB Output is correct
5 Correct 119 ms 188756 KB Output is correct
6 Correct 136 ms 188816 KB Output is correct
7 Correct 122 ms 183892 KB Output is correct
8 Correct 3073 ms 264392 KB Output is correct
9 Correct 2996 ms 265620 KB Output is correct
10 Correct 109 ms 183888 KB Output is correct
11 Correct 2887 ms 272560 KB Output is correct
12 Correct 2924 ms 272020 KB Output is correct
13 Correct 1341 ms 275632 KB Output is correct
14 Correct 116 ms 183892 KB Output is correct
15 Correct 2464 ms 265412 KB Output is correct
16 Correct 2847 ms 266208 KB Output is correct
17 Correct 2992 ms 266252 KB Output is correct
18 Correct 3053 ms 266500 KB Output is correct
19 Execution timed out 3564 ms 270328 KB Time limit exceeded
20 Halted 0 ms 0 KB -