oj.uz

Submission #865849

# Submission time Handle Problem Language Result Execution time Memory
865849 2023-10-24T23:44:40 Z AbdelmagedNour Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 54044 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N=250005,SQ=450;
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 20 ms 23644 KB Output is correct
2 Correct 24 ms 23900 KB Output is correct
3 Correct 32 ms 24400 KB Output is correct
4 Correct 26 ms 24156 KB Output is correct
5 Correct 24 ms 24144 KB Output is correct
6 Correct 36 ms 24000 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23644 KB Output is correct
2 Correct 24 ms 23900 KB Output is correct
3 Correct 32 ms 24400 KB Output is correct
4 Correct 26 ms 24156 KB Output is correct
5 Correct 24 ms 24144 KB Output is correct
6 Correct 36 ms 24000 KB Output is correct
7 Correct 28 ms 23644 KB Output is correct
8 Correct 124 ms 23888 KB Output is correct
9 Correct 453 ms 24176 KB Output is correct
10 Correct 134 ms 23892 KB Output is correct
11 Correct 164 ms 24660 KB Output is correct
12 Correct 2137 ms 24400 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23644 KB Output is correct
2 Correct 624 ms 43128 KB Output is correct
3 Correct 632 ms 42440 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23644 KB Output is correct
2 Correct 624 ms 43128 KB Output is correct
3 Correct 632 ms 42440 KB Output is correct
4 Correct 53 ms 23640 KB Output is correct
5 Correct 1155 ms 42564 KB Output is correct
6 Correct 825 ms 42708 KB Output is correct
7 Correct 2254 ms 42880 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23640 KB Output is correct
2 Correct 809 ms 50876 KB Output is correct
3 Correct 807 ms 50556 KB Output is correct
4 Correct 678 ms 52168 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23640 KB Output is correct
2 Correct 809 ms 50876 KB Output is correct
3 Correct 807 ms 50556 KB Output is correct
4 Correct 678 ms 52168 KB Output is correct
5 Correct 25 ms 23588 KB Output is correct
6 Correct 1033 ms 50840 KB Output is correct
7 Correct 1518 ms 50704 KB Output is correct
8 Correct 1136 ms 51864 KB Output is correct
9 Correct 1096 ms 51908 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24412 KB Output is correct
2 Correct 517 ms 43668 KB Output is correct
3 Correct 1543 ms 43908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24412 KB Output is correct
2 Correct 517 ms 43668 KB Output is correct
3 Correct 1543 ms 43908 KB Output is correct
4 Correct 26 ms 24460 KB Output is correct
5 Correct 1235 ms 43908 KB Output is correct
6 Correct 1528 ms 43668 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24408 KB Output is correct
2 Correct 916 ms 52244 KB Output is correct
3 Correct 981 ms 52432 KB Output is correct
4 Correct 953 ms 54044 KB Output is correct
5 Correct 22 ms 24412 KB Output is correct
6 Correct 466 ms 43688 KB Output is correct
7 Correct 1329 ms 44160 KB Output is correct
8 Correct 1894 ms 45156 KB Output is correct
9 Correct 1321 ms 45268 KB Output is correct
10 Correct 3448 ms 48060 KB Output is correct
11 Correct 2822 ms 46988 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24408 KB Output is correct
2 Correct 916 ms 52244 KB Output is correct
3 Correct 981 ms 52432 KB Output is correct
4 Correct 953 ms 54044 KB Output is correct
5 Correct 22 ms 24412 KB Output is correct
6 Correct 466 ms 43688 KB Output is correct
7 Correct 1329 ms 44160 KB Output is correct
8 Correct 1894 ms 45156 KB Output is correct
9 Correct 1321 ms 45268 KB Output is correct
10 Correct 3448 ms 48060 KB Output is correct
11 Correct 2822 ms 46988 KB Output is correct
12 Correct 32 ms 24400 KB Output is correct
13 Correct 1142 ms 52288 KB Output is correct
14 Correct 1499 ms 52900 KB Output is correct
15 Correct 1185 ms 51916 KB Output is correct
16 Correct 1261 ms 52268 KB Output is correct
17 Correct 25 ms 24408 KB Output is correct
18 Correct 1237 ms 43788 KB Output is correct
19 Correct 1763 ms 43704 KB Output is correct
20 Correct 1431 ms 45052 KB Output is correct
21 Correct 1904 ms 44988 KB Output is correct
22 Execution timed out 3535 ms 46212 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24404 KB Output is correct
2 Correct 25 ms 24988 KB Output is correct
3 Correct 34 ms 25172 KB Output is correct
4 Correct 38 ms 25024 KB Output is correct
5 Correct 24 ms 25172 KB Output is correct
6 Correct 38 ms 24924 KB Output is correct
7 Correct 26 ms 24404 KB Output is correct
8 Correct 831 ms 44628 KB Output is correct
9 Correct 768 ms 44324 KB Output is correct
10 Correct 19 ms 24228 KB Output is correct
11 Correct 1102 ms 52484 KB Output is correct
12 Correct 1024 ms 52412 KB Output is correct
13 Correct 1027 ms 54036 KB Output is correct
14 Correct 22 ms 24272 KB Output is correct
15 Correct 637 ms 43836 KB Output is correct
16 Correct 1293 ms 43740 KB Output is correct
17 Correct 1147 ms 46136 KB Output is correct
18 Correct 1233 ms 46300 KB Output is correct
19 Correct 2235 ms 48792 KB Output is correct
20 Execution timed out 3559 ms 47636 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24404 KB Output is correct
2 Correct 25 ms 24988 KB Output is correct
3 Correct 34 ms 25172 KB Output is correct
4 Correct 38 ms 25024 KB Output is correct
5 Correct 24 ms 25172 KB Output is correct
6 Correct 38 ms 24924 KB Output is correct
7 Correct 26 ms 24404 KB Output is correct
8 Correct 831 ms 44628 KB Output is correct
9 Correct 768 ms 44324 KB Output is correct
10 Correct 19 ms 24228 KB Output is correct
11 Correct 1102 ms 52484 KB Output is correct
12 Correct 1024 ms 52412 KB Output is correct
13 Correct 1027 ms 54036 KB Output is correct
14 Correct 22 ms 24272 KB Output is correct
15 Correct 637 ms 43836 KB Output is correct
16 Correct 1293 ms 43740 KB Output is correct
17 Correct 1147 ms 46136 KB Output is correct
18 Correct 1233 ms 46300 KB Output is correct
19 Correct 2235 ms 48792 KB Output is correct
20 Execution timed out 3559 ms 47636 KB Time limit exceeded
21 Halted 0 ms 0 KB -