Submission #865841

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865841	2023-10-24T23:26:37 Z	AbdelmagedNour	Inside information (BOI21_servers)	C++17	22.5 / 100	3500 ms	275544 KB

servers

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=250005,SQ=500;
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	107 ms	182868 KB	Output is correct
2	Correct	111 ms	187700 KB	Output is correct
3	Correct	120 ms	187220 KB	Output is correct
4	Correct	109 ms	187464 KB	Output is correct
5	Correct	108 ms	187372 KB	Output is correct
6	Correct	129 ms	187540 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	182868 KB	Output is correct
2	Correct	111 ms	187700 KB	Output is correct
3	Correct	120 ms	187220 KB	Output is correct
4	Correct	109 ms	187464 KB	Output is correct
5	Correct	108 ms	187372 KB	Output is correct
6	Correct	129 ms	187540 KB	Output is correct
7	Correct	121 ms	182828 KB	Output is correct
8	Correct	228 ms	185172 KB	Output is correct
9	Correct	705 ms	187664 KB	Output is correct
10	Correct	241 ms	185624 KB	Output is correct
11	Correct	333 ms	185524 KB	Output is correct
12	Correct	3253 ms	185736 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	182944 KB	Output is correct
2	Correct	3472 ms	262956 KB	Output is correct
3	Correct	3480 ms	265180 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	182944 KB	Output is correct
2	Correct	3472 ms	262956 KB	Output is correct
3	Correct	3480 ms	265180 KB	Output is correct
4	Correct	156 ms	183892 KB	Output is correct
5	Execution timed out	3552 ms	255492 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	182884 KB	Output is correct
2	Correct	3385 ms	268684 KB	Output is correct
3	Correct	3432 ms	272160 KB	Output is correct
4	Correct	1567 ms	275544 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	182884 KB	Output is correct
2	Correct	3385 ms	268684 KB	Output is correct
3	Correct	3432 ms	272160 KB	Output is correct
4	Correct	1567 ms	275544 KB	Output is correct
5	Correct	105 ms	183892 KB	Output is correct
6	Execution timed out	3536 ms	270724 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	183632 KB	Output is correct
2	Correct	2830 ms	264056 KB	Output is correct
3	Correct	3336 ms	266000 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	183632 KB	Output is correct
2	Correct	2830 ms	264056 KB	Output is correct
3	Correct	3336 ms	266000 KB	Output is correct
4	Correct	112 ms	183740 KB	Output is correct
5	Execution timed out	3589 ms	264376 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	183664 KB	Output is correct
2	Correct	3449 ms	270408 KB	Output is correct
3	Execution timed out	3557 ms	268708 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	183664 KB	Output is correct
2	Correct	3449 ms	270408 KB	Output is correct
3	Execution timed out	3557 ms	268708 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	183868 KB	Output is correct
2	Correct	117 ms	188500 KB	Output is correct
3	Correct	124 ms	188756 KB	Output is correct
4	Correct	127 ms	188756 KB	Output is correct
5	Correct	118 ms	188892 KB	Output is correct
6	Correct	124 ms	188752 KB	Output is correct
7	Correct	115 ms	183776 KB	Output is correct
8	Execution timed out	3558 ms	264268 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	183868 KB	Output is correct
2	Correct	117 ms	188500 KB	Output is correct
3	Correct	124 ms	188756 KB	Output is correct
4	Correct	127 ms	188756 KB	Output is correct
5	Correct	118 ms	188892 KB	Output is correct
6	Correct	124 ms	188752 KB	Output is correct
7	Correct	115 ms	183776 KB	Output is correct
8	Execution timed out	3558 ms	264268 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #865841

Compilation message