oj.uz

Submission #865843

# Submission time Handle Problem Language Result Execution time Memory
865843 2023-10-24T23:29:56 Z AbdelmagedNour Inside information (BOI21_servers) C++17
37.5 / 100
 3500 ms 272648 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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){
	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(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 105 ms 185748 KB Output is correct
2 Correct 110 ms 188756 KB Output is correct
3 Correct 119 ms 188752 KB Output is correct
4 Correct 114 ms 188844 KB Output is correct
5 Correct 111 ms 188756 KB Output is correct
6 Correct 134 ms 188920 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 185748 KB Output is correct
2 Correct 110 ms 188756 KB Output is correct
3 Correct 119 ms 188752 KB Output is correct
4 Correct 114 ms 188844 KB Output is correct
5 Correct 111 ms 188756 KB Output is correct
6 Correct 134 ms 188920 KB Output is correct
7 Correct 123 ms 185940 KB Output is correct
8 Correct 277 ms 188240 KB Output is correct
9 Correct 903 ms 188400 KB Output is correct
10 Correct 303 ms 188488 KB Output is correct
11 Correct 153 ms 188500 KB Output is correct
12 Correct 1495 ms 188768 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 185944 KB Output is correct
2 Correct 2785 ms 264396 KB Output is correct
3 Correct 2798 ms 262740 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 185944 KB Output is correct
2 Correct 2785 ms 264396 KB Output is correct
3 Correct 2798 ms 262740 KB Output is correct
4 Correct 154 ms 184916 KB Output is correct
5 Execution timed out 3613 ms 259348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184912 KB Output is correct
2 Correct 2700 ms 269080 KB Output is correct
3 Correct 2716 ms 268756 KB Output is correct
4 Correct 1224 ms 272628 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184912 KB Output is correct
2 Correct 2700 ms 269080 KB Output is correct
3 Correct 2716 ms 268756 KB Output is correct
4 Correct 1224 ms 272628 KB Output is correct
5 Correct 108 ms 184968 KB Output is correct
6 Correct 2886 ms 268820 KB Output is correct
7 Correct 3097 ms 271200 KB Output is correct
8 Correct 3051 ms 268796 KB Output is correct
9 Correct 3038 ms 268628 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 185092 KB Output is correct
2 Correct 2206 ms 262364 KB Output is correct
3 Correct 2611 ms 262980 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 185092 KB Output is correct
2 Correct 2206 ms 262364 KB Output is correct
3 Correct 2611 ms 262980 KB Output is correct
4 Correct 113 ms 184912 KB Output is correct
5 Correct 3221 ms 262428 KB Output is correct
6 Correct 2867 ms 265728 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 2686 ms 269084 KB Output is correct
3 Correct 2735 ms 268912 KB Output is correct
4 Correct 1238 ms 272336 KB Output is correct
5 Correct 107 ms 184912 KB Output is correct
6 Correct 2275 ms 262492 KB Output is correct
7 Correct 2626 ms 262676 KB Output is correct
8 Correct 2800 ms 263156 KB Output is correct
9 Correct 2824 ms 263500 KB Output is correct
10 Execution timed out 3550 ms 267284 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 2686 ms 269084 KB Output is correct
3 Correct 2735 ms 268912 KB Output is correct
4 Correct 1238 ms 272336 KB Output is correct
5 Correct 107 ms 184912 KB Output is correct
6 Correct 2275 ms 262492 KB Output is correct
7 Correct 2626 ms 262676 KB Output is correct
8 Correct 2800 ms 263156 KB Output is correct
9 Correct 2824 ms 263500 KB Output is correct
10 Execution timed out 3550 ms 267284 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184960 KB Output is correct
2 Correct 115 ms 187476 KB Output is correct
3 Correct 125 ms 187220 KB Output is correct
4 Correct 116 ms 187472 KB Output is correct
5 Correct 111 ms 187476 KB Output is correct
6 Correct 151 ms 187592 KB Output is correct
7 Correct 119 ms 185032 KB Output is correct
8 Correct 2904 ms 262940 KB Output is correct
9 Correct 2823 ms 262820 KB Output is correct
10 Correct 102 ms 184860 KB Output is correct
11 Correct 2716 ms 268848 KB Output is correct
12 Correct 2721 ms 269112 KB Output is correct
13 Correct 1273 ms 272648 KB Output is correct
14 Correct 107 ms 184912 KB Output is correct
15 Correct 2247 ms 262160 KB Output is correct
16 Correct 2693 ms 262704 KB Output is correct
17 Correct 2820 ms 262992 KB Output is correct
18 Correct 2872 ms 263324 KB Output is correct
19 Execution timed out 3573 ms 266952 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184960 KB Output is correct
2 Correct 115 ms 187476 KB Output is correct
3 Correct 125 ms 187220 KB Output is correct
4 Correct 116 ms 187472 KB Output is correct
5 Correct 111 ms 187476 KB Output is correct
6 Correct 151 ms 187592 KB Output is correct
7 Correct 119 ms 185032 KB Output is correct
8 Correct 2904 ms 262940 KB Output is correct
9 Correct 2823 ms 262820 KB Output is correct
10 Correct 102 ms 184860 KB Output is correct
11 Correct 2716 ms 268848 KB Output is correct
12 Correct 2721 ms 269112 KB Output is correct
13 Correct 1273 ms 272648 KB Output is correct
14 Correct 107 ms 184912 KB Output is correct
15 Correct 2247 ms 262160 KB Output is correct
16 Correct 2693 ms 262704 KB Output is correct
17 Correct 2820 ms 262992 KB Output is correct
18 Correct 2872 ms 263324 KB Output is correct
19 Execution timed out 3573 ms 266952 KB Time limit exceeded
20 Halted 0 ms 0 KB -