oj.uz

Submission #865850

# Submission time Handle Problem Language Result Execution time Memory
865850 2023-10-24T23:44:57 Z AbdelmagedNour Inside information (BOI21_servers) C++17
40 / 100
 3500 ms 54284 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N=250005,SQ=350;
vector<vector<pair<int,int>>>adj(N);
vector<int>cur_adj[N],order;
int in[N],out[N],dep[N],p[N][18],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(int i=cur_adj[v].size()-1;i>=0;i--){
		int u=cur_adj[v][i];
		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_back(B[i]);
			cur_adj[B[i]].push_back(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 21 ms 24152 KB Output is correct
2 Correct 26 ms 24944 KB Output is correct
3 Correct 48 ms 25172 KB Output is correct
4 Correct 29 ms 25168 KB Output is correct
5 Correct 27 ms 25176 KB Output is correct
6 Correct 52 ms 25092 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24152 KB Output is correct
2 Correct 26 ms 24944 KB Output is correct
3 Correct 48 ms 25172 KB Output is correct
4 Correct 29 ms 25168 KB Output is correct
5 Correct 27 ms 25176 KB Output is correct
6 Correct 52 ms 25092 KB Output is correct
7 Correct 31 ms 24400 KB Output is correct
8 Correct 99 ms 24736 KB Output is correct
9 Correct 328 ms 25056 KB Output is correct
10 Correct 106 ms 24828 KB Output is correct
11 Correct 95 ms 24912 KB Output is correct
12 Correct 1010 ms 24900 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24400 KB Output is correct
2 Correct 939 ms 44380 KB Output is correct
3 Correct 867 ms 44396 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24400 KB Output is correct
2 Correct 939 ms 44380 KB Output is correct
3 Correct 867 ms 44396 KB Output is correct
4 Correct 55 ms 24412 KB Output is correct
5 Correct 1427 ms 43996 KB Output is correct
6 Correct 1047 ms 44052 KB Output is correct
7 Correct 2564 ms 43908 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24404 KB Output is correct
2 Correct 1425 ms 52284 KB Output is correct
3 Correct 1159 ms 52680 KB Output is correct
4 Correct 1108 ms 54052 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24404 KB Output is correct
2 Correct 1425 ms 52284 KB Output is correct
3 Correct 1159 ms 52680 KB Output is correct
4 Correct 1108 ms 54052 KB Output is correct
5 Correct 21 ms 24344 KB Output is correct
6 Correct 1435 ms 52412 KB Output is correct
7 Correct 1572 ms 52828 KB Output is correct
8 Correct 1456 ms 50436 KB Output is correct
9 Correct 1490 ms 50376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23640 KB Output is correct
2 Correct 615 ms 42024 KB Output is correct
3 Correct 1740 ms 42188 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23640 KB Output is correct
2 Correct 615 ms 42024 KB Output is correct
3 Correct 1740 ms 42188 KB Output is correct
4 Correct 24 ms 23644 KB Output is correct
5 Correct 1270 ms 42052 KB Output is correct
6 Correct 1952 ms 41964 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23640 KB Output is correct
2 Correct 1193 ms 50700 KB Output is correct
3 Correct 1210 ms 50564 KB Output is correct
4 Correct 1050 ms 52104 KB Output is correct
5 Correct 19 ms 23640 KB Output is correct
6 Correct 582 ms 41932 KB Output is correct
7 Correct 1681 ms 42204 KB Output is correct
8 Correct 1968 ms 43280 KB Output is correct
9 Correct 1690 ms 43256 KB Output is correct
10 Correct 3494 ms 45736 KB Output is correct
11 Execution timed out 3536 ms 45188 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23640 KB Output is correct
2 Correct 1193 ms 50700 KB Output is correct
3 Correct 1210 ms 50564 KB Output is correct
4 Correct 1050 ms 52104 KB Output is correct
5 Correct 19 ms 23640 KB Output is correct
6 Correct 582 ms 41932 KB Output is correct
7 Correct 1681 ms 42204 KB Output is correct
8 Correct 1968 ms 43280 KB Output is correct
9 Correct 1690 ms 43256 KB Output is correct
10 Correct 3494 ms 45736 KB Output is correct
11 Execution timed out 3536 ms 45188 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23640 KB Output is correct
2 Correct 25 ms 23900 KB Output is correct
3 Correct 34 ms 24112 KB Output is correct
4 Correct 25 ms 23900 KB Output is correct
5 Correct 25 ms 24148 KB Output is correct
6 Correct 37 ms 23904 KB Output is correct
7 Correct 26 ms 23644 KB Output is correct
8 Correct 1350 ms 42424 KB Output is correct
9 Correct 913 ms 42436 KB Output is correct
10 Correct 19 ms 24156 KB Output is correct
11 Correct 1271 ms 52548 KB Output is correct
12 Correct 1239 ms 52748 KB Output is correct
13 Correct 998 ms 54284 KB Output is correct
14 Correct 20 ms 24152 KB Output is correct
15 Correct 606 ms 44044 KB Output is correct
16 Correct 1824 ms 43488 KB Output is correct
17 Correct 2647 ms 43192 KB Output is correct
18 Correct 1436 ms 43452 KB Output is correct
19 Correct 2965 ms 45712 KB Output is correct
20 Execution timed out 3555 ms 44856 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23640 KB Output is correct
2 Correct 25 ms 23900 KB Output is correct
3 Correct 34 ms 24112 KB Output is correct
4 Correct 25 ms 23900 KB Output is correct
5 Correct 25 ms 24148 KB Output is correct
6 Correct 37 ms 23904 KB Output is correct
7 Correct 26 ms 23644 KB Output is correct
8 Correct 1350 ms 42424 KB Output is correct
9 Correct 913 ms 42436 KB Output is correct
10 Correct 19 ms 24156 KB Output is correct
11 Correct 1271 ms 52548 KB Output is correct
12 Correct 1239 ms 52748 KB Output is correct
13 Correct 998 ms 54284 KB Output is correct
14 Correct 20 ms 24152 KB Output is correct
15 Correct 606 ms 44044 KB Output is correct
16 Correct 1824 ms 43488 KB Output is correct
17 Correct 2647 ms 43192 KB Output is correct
18 Correct 1436 ms 43452 KB Output is correct
19 Correct 2965 ms 45712 KB Output is correct
20 Execution timed out 3555 ms 44856 KB Time limit exceeded
21 Halted 0 ms 0 KB -