oj.uz

Submission #865838

# Submission time Handle Problem Language Result Execution time Memory
865838 2023-10-24T23:22:03 Z AbdelmagedNour Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 270444 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=250005,SQ=350;
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;
	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 103 ms 183888 KB Output is correct
2 Correct 112 ms 188544 KB Output is correct
3 Correct 118 ms 188648 KB Output is correct
4 Correct 109 ms 188692 KB Output is correct
5 Correct 108 ms 188756 KB Output is correct
6 Correct 121 ms 188832 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 103 ms 183888 KB Output is correct
2 Correct 112 ms 188544 KB Output is correct
3 Correct 118 ms 188648 KB Output is correct
4 Correct 109 ms 188692 KB Output is correct
5 Correct 108 ms 188756 KB Output is correct
6 Correct 121 ms 188832 KB Output is correct
7 Correct 136 ms 183892 KB Output is correct
8 Correct 188 ms 186368 KB Output is correct
9 Correct 517 ms 188752 KB Output is correct
10 Correct 185 ms 186452 KB Output is correct
11 Correct 160 ms 186616 KB Output is correct
12 Correct 1313 ms 186852 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 183744 KB Output is correct
2 Execution timed out 3569 ms 253792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 183744 KB Output is correct
2 Execution timed out 3569 ms 253792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 183892 KB Output is correct
2 Execution timed out 3540 ms 270444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 183892 KB Output is correct
2 Execution timed out 3540 ms 270444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 183888 KB Output is correct
2 Execution timed out 3551 ms 262924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 183888 KB Output is correct
2 Execution timed out 3551 ms 262924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 107 ms 183720 KB Output is correct
2 Execution timed out 3572 ms 270092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 107 ms 183720 KB Output is correct
2 Execution timed out 3572 ms 270092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 183636 KB Output is correct
2 Correct 112 ms 188452 KB Output is correct
3 Correct 119 ms 188496 KB Output is correct
4 Correct 112 ms 188488 KB Output is correct
5 Correct 110 ms 188724 KB Output is correct
6 Correct 124 ms 188504 KB Output is correct
7 Correct 116 ms 183636 KB Output is correct
8 Execution timed out 3605 ms 254612 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 183636 KB Output is correct
2 Correct 112 ms 188452 KB Output is correct
3 Correct 119 ms 188496 KB Output is correct
4 Correct 112 ms 188488 KB Output is correct
5 Correct 110 ms 188724 KB Output is correct
6 Correct 124 ms 188504 KB Output is correct
7 Correct 116 ms 183636 KB Output is correct
8 Execution timed out 3605 ms 254612 KB Time limit exceeded
9 Halted 0 ms 0 KB -