oj.uz

Submission #865845

# Submission time Handle Problem Language Result Execution time Memory
865845 2023-10-24T23:34:14 Z AbdelmagedNour Inside information (BOI21_servers) C++17
37.5 / 100
 3500 ms 272652 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){
	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 105 ms 184916 KB Output is correct
2 Correct 110 ms 187244 KB Output is correct
3 Correct 123 ms 187216 KB Output is correct
4 Correct 112 ms 187216 KB Output is correct
5 Correct 115 ms 187476 KB Output is correct
6 Correct 123 ms 187452 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184916 KB Output is correct
2 Correct 110 ms 187244 KB Output is correct
3 Correct 123 ms 187216 KB Output is correct
4 Correct 112 ms 187216 KB Output is correct
5 Correct 115 ms 187476 KB Output is correct
6 Correct 123 ms 187452 KB Output is correct
7 Correct 120 ms 185168 KB Output is correct
8 Correct 258 ms 187312 KB Output is correct
9 Correct 698 ms 187976 KB Output is correct
10 Correct 277 ms 187352 KB Output is correct
11 Correct 151 ms 187420 KB Output is correct
12 Correct 1226 ms 187628 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 113 ms 184908 KB Output is correct
2 Correct 2678 ms 262944 KB Output is correct
3 Correct 2694 ms 262740 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 113 ms 184908 KB Output is correct
2 Correct 2678 ms 262944 KB Output is correct
3 Correct 2694 ms 262740 KB Output is correct
4 Correct 139 ms 184912 KB Output is correct
5 Execution timed out 3535 ms 262316 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 184916 KB Output is correct
2 Correct 2681 ms 269296 KB Output is correct
3 Correct 2701 ms 269116 KB Output is correct
4 Correct 1263 ms 272512 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 184916 KB Output is correct
2 Correct 2681 ms 269296 KB Output is correct
3 Correct 2701 ms 269116 KB Output is correct
4 Correct 1263 ms 272512 KB Output is correct
5 Correct 107 ms 185072 KB Output is correct
6 Correct 2842 ms 268696 KB Output is correct
7 Correct 2229 ms 270996 KB Output is correct
8 Correct 2954 ms 268600 KB Output is correct
9 Correct 2946 ms 268888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184916 KB Output is correct
2 Correct 2318 ms 262112 KB Output is correct
3 Correct 2667 ms 262916 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184916 KB Output is correct
2 Correct 2318 ms 262112 KB Output is correct
3 Correct 2667 ms 262916 KB Output is correct
4 Correct 108 ms 184916 KB Output is correct
5 Correct 3335 ms 262180 KB Output is correct
6 Correct 2843 ms 262868 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184916 KB Output is correct
2 Correct 2674 ms 268912 KB Output is correct
3 Correct 2683 ms 268872 KB Output is correct
4 Correct 1230 ms 272452 KB Output is correct
5 Correct 104 ms 184948 KB Output is correct
6 Correct 2310 ms 262076 KB Output is correct
7 Correct 2666 ms 263016 KB Output is correct
8 Correct 2669 ms 263176 KB Output is correct
9 Correct 2670 ms 263148 KB Output is correct
10 Execution timed out 3578 ms 267044 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184916 KB Output is correct
2 Correct 2674 ms 268912 KB Output is correct
3 Correct 2683 ms 268872 KB Output is correct
4 Correct 1230 ms 272452 KB Output is correct
5 Correct 104 ms 184948 KB Output is correct
6 Correct 2310 ms 262076 KB Output is correct
7 Correct 2666 ms 263016 KB Output is correct
8 Correct 2669 ms 263176 KB Output is correct
9 Correct 2670 ms 263148 KB Output is correct
10 Execution timed out 3578 ms 267044 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 112 ms 187216 KB Output is correct
3 Correct 124 ms 187472 KB Output is correct
4 Correct 111 ms 187220 KB Output is correct
5 Correct 112 ms 187420 KB Output is correct
6 Correct 125 ms 187216 KB Output is correct
7 Correct 115 ms 185068 KB Output is correct
8 Correct 2663 ms 263176 KB Output is correct
9 Correct 2655 ms 262744 KB Output is correct
10 Correct 102 ms 184912 KB Output is correct
11 Correct 2640 ms 268808 KB Output is correct
12 Correct 2685 ms 269144 KB Output is correct
13 Correct 1231 ms 272652 KB Output is correct
14 Correct 104 ms 184916 KB Output is correct
15 Correct 2286 ms 262448 KB Output is correct
16 Correct 2666 ms 262844 KB Output is correct
17 Correct 2742 ms 263236 KB Output is correct
18 Correct 2674 ms 263132 KB Output is correct
19 Execution timed out 3535 ms 267056 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 112 ms 187216 KB Output is correct
3 Correct 124 ms 187472 KB Output is correct
4 Correct 111 ms 187220 KB Output is correct
5 Correct 112 ms 187420 KB Output is correct
6 Correct 125 ms 187216 KB Output is correct
7 Correct 115 ms 185068 KB Output is correct
8 Correct 2663 ms 263176 KB Output is correct
9 Correct 2655 ms 262744 KB Output is correct
10 Correct 102 ms 184912 KB Output is correct
11 Correct 2640 ms 268808 KB Output is correct
12 Correct 2685 ms 269144 KB Output is correct
13 Correct 1231 ms 272652 KB Output is correct
14 Correct 104 ms 184916 KB Output is correct
15 Correct 2286 ms 262448 KB Output is correct
16 Correct 2666 ms 262844 KB Output is correct
17 Correct 2742 ms 263236 KB Output is correct
18 Correct 2674 ms 263132 KB Output is correct
19 Execution timed out 3535 ms 267056 KB Time limit exceeded
20 Halted 0 ms 0 KB -