oj.uz

Submission #865846

# Submission time Handle Problem Language Result Execution time Memory
865846 2023-10-24T23:38:16 Z AbdelmagedNour Inside information (BOI21_servers) C++17
37.5 / 100
 3500 ms 272776 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N=250005,SQ=650;
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<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(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);
	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_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=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 104 ms 184912 KB Output is correct
2 Correct 114 ms 187224 KB Output is correct
3 Correct 125 ms 187472 KB Output is correct
4 Correct 115 ms 187472 KB Output is correct
5 Correct 114 ms 187476 KB Output is correct
6 Correct 128 ms 187456 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184912 KB Output is correct
2 Correct 114 ms 187224 KB Output is correct
3 Correct 125 ms 187472 KB Output is correct
4 Correct 115 ms 187472 KB Output is correct
5 Correct 114 ms 187476 KB Output is correct
6 Correct 128 ms 187456 KB Output is correct
7 Correct 121 ms 184968 KB Output is correct
8 Correct 256 ms 187220 KB Output is correct
9 Correct 735 ms 187604 KB Output is correct
10 Correct 279 ms 187268 KB Output is correct
11 Correct 145 ms 187472 KB Output is correct
12 Correct 1245 ms 187752 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 111 ms 185064 KB Output is correct
2 Correct 2697 ms 262932 KB Output is correct
3 Correct 2743 ms 262672 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 111 ms 185064 KB Output is correct
2 Correct 2697 ms 262932 KB Output is correct
3 Correct 2743 ms 262672 KB Output is correct
4 Correct 143 ms 184916 KB Output is correct
5 Execution timed out 3602 ms 262828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 184920 KB Output is correct
2 Correct 2736 ms 270600 KB Output is correct
3 Correct 2738 ms 270664 KB Output is correct
4 Correct 1307 ms 272408 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 184920 KB Output is correct
2 Correct 2736 ms 270600 KB Output is correct
3 Correct 2738 ms 270664 KB Output is correct
4 Correct 1307 ms 272408 KB Output is correct
5 Correct 109 ms 184916 KB Output is correct
6 Correct 2942 ms 270924 KB Output is correct
7 Correct 2261 ms 270964 KB Output is correct
8 Correct 3094 ms 270756 KB Output is correct
9 Correct 3058 ms 270664 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184888 KB Output is correct
2 Correct 2315 ms 262248 KB Output is correct
3 Correct 2663 ms 262748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184888 KB Output is correct
2 Correct 2315 ms 262248 KB Output is correct
3 Correct 2663 ms 262748 KB Output is correct
4 Correct 117 ms 185080 KB Output is correct
5 Correct 3357 ms 262584 KB Output is correct
6 Correct 2901 ms 262788 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184848 KB Output is correct
2 Correct 2700 ms 271156 KB Output is correct
3 Correct 2731 ms 270840 KB Output is correct
4 Correct 1241 ms 272592 KB Output is correct
5 Correct 103 ms 184912 KB Output is correct
6 Correct 2417 ms 262320 KB Output is correct
7 Correct 2713 ms 262864 KB Output is correct
8 Correct 2777 ms 263152 KB Output is correct
9 Correct 2726 ms 263312 KB Output is correct
10 Execution timed out 3562 ms 267608 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184848 KB Output is correct
2 Correct 2700 ms 271156 KB Output is correct
3 Correct 2731 ms 270840 KB Output is correct
4 Correct 1241 ms 272592 KB Output is correct
5 Correct 103 ms 184912 KB Output is correct
6 Correct 2417 ms 262320 KB Output is correct
7 Correct 2713 ms 262864 KB Output is correct
8 Correct 2777 ms 263152 KB Output is correct
9 Correct 2726 ms 263312 KB Output is correct
10 Execution timed out 3562 ms 267608 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184916 KB Output is correct
2 Correct 113 ms 187216 KB Output is correct
3 Correct 126 ms 187328 KB Output is correct
4 Correct 112 ms 187476 KB Output is correct
5 Correct 112 ms 187476 KB Output is correct
6 Correct 126 ms 187296 KB Output is correct
7 Correct 111 ms 185136 KB Output is correct
8 Correct 2708 ms 262912 KB Output is correct
9 Correct 2752 ms 262620 KB Output is correct
10 Correct 106 ms 184916 KB Output is correct
11 Correct 2700 ms 270988 KB Output is correct
12 Correct 2709 ms 270604 KB Output is correct
13 Correct 1262 ms 272776 KB Output is correct
14 Correct 106 ms 184988 KB Output is correct
15 Correct 2317 ms 262480 KB Output is correct
16 Correct 2669 ms 262804 KB Output is correct
17 Correct 2692 ms 263320 KB Output is correct
18 Correct 2763 ms 263308 KB Output is correct
19 Execution timed out 3575 ms 267776 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184916 KB Output is correct
2 Correct 113 ms 187216 KB Output is correct
3 Correct 126 ms 187328 KB Output is correct
4 Correct 112 ms 187476 KB Output is correct
5 Correct 112 ms 187476 KB Output is correct
6 Correct 126 ms 187296 KB Output is correct
7 Correct 111 ms 185136 KB Output is correct
8 Correct 2708 ms 262912 KB Output is correct
9 Correct 2752 ms 262620 KB Output is correct
10 Correct 106 ms 184916 KB Output is correct
11 Correct 2700 ms 270988 KB Output is correct
12 Correct 2709 ms 270604 KB Output is correct
13 Correct 1262 ms 272776 KB Output is correct
14 Correct 106 ms 184988 KB Output is correct
15 Correct 2317 ms 262480 KB Output is correct
16 Correct 2669 ms 262804 KB Output is correct
17 Correct 2692 ms 263320 KB Output is correct
18 Correct 2763 ms 263308 KB Output is correct
19 Execution timed out 3575 ms 267776 KB Time limit exceeded
20 Halted 0 ms 0 KB -