oj.uz

Submission #865844

# Submission time Handle Problem Language Result Execution time Memory
865844 2023-10-24T23:31:57 Z AbdelmagedNour Inside information (BOI21_servers) C++17
37.5 / 100
 3500 ms 272548 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 184912 KB Output is correct
2 Correct 111 ms 187308 KB Output is correct
3 Correct 118 ms 187432 KB Output is correct
4 Correct 111 ms 187220 KB Output is correct
5 Correct 114 ms 187472 KB Output is correct
6 Correct 124 ms 187220 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184912 KB Output is correct
2 Correct 111 ms 187308 KB Output is correct
3 Correct 118 ms 187432 KB Output is correct
4 Correct 111 ms 187220 KB Output is correct
5 Correct 114 ms 187472 KB Output is correct
6 Correct 124 ms 187220 KB Output is correct
7 Correct 124 ms 185068 KB Output is correct
8 Correct 289 ms 187216 KB Output is correct
9 Correct 932 ms 187472 KB Output is correct
10 Correct 306 ms 187220 KB Output is correct
11 Correct 159 ms 187700 KB Output is correct
12 Correct 1502 ms 187988 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 184904 KB Output is correct
2 Correct 2691 ms 262820 KB Output is correct
3 Correct 2673 ms 262916 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 184904 KB Output is correct
2 Correct 2691 ms 262820 KB Output is correct
3 Correct 2673 ms 262916 KB Output is correct
4 Correct 157 ms 184916 KB Output is correct
5 Execution timed out 3559 ms 259488 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 2690 ms 269204 KB Output is correct
3 Correct 2701 ms 268840 KB Output is correct
4 Correct 1220 ms 272548 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184912 KB Output is correct
2 Correct 2690 ms 269204 KB Output is correct
3 Correct 2701 ms 268840 KB Output is correct
4 Correct 1220 ms 272548 KB Output is correct
5 Correct 106 ms 184936 KB Output is correct
6 Correct 2893 ms 269140 KB Output is correct
7 Correct 3095 ms 270860 KB Output is correct
8 Correct 3058 ms 269128 KB Output is correct
9 Correct 3078 ms 269192 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184916 KB Output is correct
2 Correct 2192 ms 262064 KB Output is correct
3 Correct 2588 ms 262904 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 184916 KB Output is correct
2 Correct 2192 ms 262064 KB Output is correct
3 Correct 2588 ms 262904 KB Output is correct
4 Correct 113 ms 184916 KB Output is correct
5 Correct 3206 ms 262436 KB Output is correct
6 Correct 2836 ms 262844 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 102 ms 184916 KB Output is correct
2 Correct 2718 ms 269448 KB Output is correct
3 Correct 2736 ms 269148 KB Output is correct
4 Correct 1258 ms 272388 KB Output is correct
5 Correct 104 ms 184928 KB Output is correct
6 Correct 2189 ms 262348 KB Output is correct
7 Correct 2567 ms 262688 KB Output is correct
8 Correct 2617 ms 263176 KB Output is correct
9 Correct 2677 ms 262996 KB Output is correct
10 Execution timed out 3574 ms 266784 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 184916 KB Output is correct
2 Correct 2718 ms 269448 KB Output is correct
3 Correct 2736 ms 269148 KB Output is correct
4 Correct 1258 ms 272388 KB Output is correct
5 Correct 104 ms 184928 KB Output is correct
6 Correct 2189 ms 262348 KB Output is correct
7 Correct 2567 ms 262688 KB Output is correct
8 Correct 2617 ms 263176 KB Output is correct
9 Correct 2677 ms 262996 KB Output is correct
10 Execution timed out 3574 ms 266784 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184916 KB Output is correct
2 Correct 112 ms 187252 KB Output is correct
3 Correct 119 ms 187668 KB Output is correct
4 Correct 112 ms 187220 KB Output is correct
5 Correct 111 ms 187472 KB Output is correct
6 Correct 124 ms 187228 KB Output is correct
7 Correct 115 ms 185108 KB Output is correct
8 Correct 2654 ms 262720 KB Output is correct
9 Correct 2699 ms 262924 KB Output is correct
10 Correct 104 ms 184880 KB Output is correct
11 Correct 2707 ms 269100 KB Output is correct
12 Correct 2714 ms 268848 KB Output is correct
13 Correct 1261 ms 272376 KB Output is correct
14 Correct 105 ms 184908 KB Output is correct
15 Correct 2231 ms 262152 KB Output is correct
16 Correct 2576 ms 262720 KB Output is correct
17 Correct 2701 ms 263320 KB Output is correct
18 Correct 2720 ms 263228 KB Output is correct
19 Execution timed out 3543 ms 266832 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184916 KB Output is correct
2 Correct 112 ms 187252 KB Output is correct
3 Correct 119 ms 187668 KB Output is correct
4 Correct 112 ms 187220 KB Output is correct
5 Correct 111 ms 187472 KB Output is correct
6 Correct 124 ms 187228 KB Output is correct
7 Correct 115 ms 185108 KB Output is correct
8 Correct 2654 ms 262720 KB Output is correct
9 Correct 2699 ms 262924 KB Output is correct
10 Correct 104 ms 184880 KB Output is correct
11 Correct 2707 ms 269100 KB Output is correct
12 Correct 2714 ms 268848 KB Output is correct
13 Correct 1261 ms 272376 KB Output is correct
14 Correct 105 ms 184908 KB Output is correct
15 Correct 2231 ms 262152 KB Output is correct
16 Correct 2576 ms 262720 KB Output is correct
17 Correct 2701 ms 263320 KB Output is correct
18 Correct 2720 ms 263228 KB Output is correct
19 Execution timed out 3543 ms 266832 KB Time limit exceeded
20 Halted 0 ms 0 KB -