oj.uz

Submission #865839

# Submission time Handle Problem Language Result Execution time Memory
865839 2023-10-24T23:24:47 Z AbdelmagedNour Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 248044 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=250005,SQ=100;
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;
	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 102 ms 182868 KB Output is correct
2 Correct 119 ms 187160 KB Output is correct
3 Correct 125 ms 187472 KB Output is correct
4 Correct 112 ms 187220 KB Output is correct
5 Correct 114 ms 187476 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 102 ms 182868 KB Output is correct
2 Correct 119 ms 187160 KB Output is correct
3 Correct 125 ms 187472 KB Output is correct
4 Correct 112 ms 187220 KB Output is correct
5 Correct 114 ms 187476 KB Output is correct
6 Correct 124 ms 187220 KB Output is correct
7 Correct 125 ms 182864 KB Output is correct
8 Correct 135 ms 185312 KB Output is correct
9 Correct 221 ms 187456 KB Output is correct
10 Correct 136 ms 185544 KB Output is correct
11 Correct 145 ms 185452 KB Output is correct
12 Correct 711 ms 185568 KB Output is correct

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 182880 KB Output is correct
2 Execution timed out 3533 ms 247780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 182880 KB Output is correct
2 Execution timed out 3533 ms 247780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 100 ms 182864 KB Output is correct
2 Execution timed out 3538 ms 248044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 100 ms 182864 KB Output is correct
2 Execution timed out 3538 ms 248044 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 182844 KB Output is correct
2 Correct 113 ms 187360 KB Output is correct
3 Correct 126 ms 187592 KB Output is correct
4 Correct 115 ms 187216 KB Output is correct
5 Correct 112 ms 187356 KB Output is correct
6 Correct 127 ms 187260 KB Output is correct
7 Correct 116 ms 183232 KB Output is correct
8 Execution timed out 3538 ms 225328 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 182844 KB Output is correct
2 Correct 113 ms 187360 KB Output is correct
3 Correct 126 ms 187592 KB Output is correct
4 Correct 115 ms 187216 KB Output is correct
5 Correct 112 ms 187356 KB Output is correct
6 Correct 127 ms 187260 KB Output is correct
7 Correct 116 ms 183232 KB Output is correct
8 Execution timed out 3538 ms 225328 KB Time limit exceeded
9 Halted 0 ms 0 KB -