oj.uz

Submission #865840

# Submission time Handle Problem Language Result Execution time Memory
865840 2023-10-24T23:26:01 Z AbdelmagedNour Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 267308 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;
	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 100 ms 182868 KB Output is correct
2 Correct 113 ms 187336 KB Output is correct
3 Correct 120 ms 187464 KB Output is correct
4 Correct 111 ms 187384 KB Output is correct
5 Correct 109 ms 187476 KB Output is correct
6 Correct 122 ms 187420 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 100 ms 182868 KB Output is correct
2 Correct 113 ms 187336 KB Output is correct
3 Correct 120 ms 187464 KB Output is correct
4 Correct 111 ms 187384 KB Output is correct
5 Correct 109 ms 187476 KB Output is correct
6 Correct 122 ms 187420 KB Output is correct
7 Correct 122 ms 182868 KB Output is correct
8 Correct 193 ms 185124 KB Output is correct
9 Correct 492 ms 187476 KB Output is correct
10 Correct 188 ms 185172 KB Output is correct
11 Correct 163 ms 185500 KB Output is correct
12 Correct 1319 ms 185740 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 109 ms 183004 KB Output is correct
2 Execution timed out 3593 ms 253172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 109 ms 183004 KB Output is correct
2 Execution timed out 3593 ms 253172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 182868 KB Output is correct
2 Execution timed out 3531 ms 259600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 182868 KB Output is correct
2 Execution timed out 3531 ms 259600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 101 ms 182888 KB Output is correct
2 Execution timed out 3580 ms 267152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 101 ms 182888 KB Output is correct
2 Execution timed out 3580 ms 267152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 103 ms 182884 KB Output is correct
2 Correct 108 ms 187216 KB Output is correct
3 Correct 118 ms 187220 KB Output is correct
4 Correct 110 ms 187220 KB Output is correct
5 Correct 117 ms 187476 KB Output is correct
6 Correct 122 ms 187220 KB Output is correct
7 Correct 108 ms 182868 KB Output is correct
8 Execution timed out 3569 ms 253216 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 103 ms 182884 KB Output is correct
2 Correct 108 ms 187216 KB Output is correct
3 Correct 118 ms 187220 KB Output is correct
4 Correct 110 ms 187220 KB Output is correct
5 Correct 117 ms 187476 KB Output is correct
6 Correct 122 ms 187220 KB Output is correct
7 Correct 108 ms 182868 KB Output is correct
8 Execution timed out 3569 ms 253216 KB Time limit exceeded
9 Halted 0 ms 0 KB -