oj.uz

Submission #865848

# Submission time Handle Problem Language Result Execution time Memory
865848 2023-10-24T23:42:11 Z AbdelmagedNour Inside information (BOI21_servers) C++17
100 / 100
 2866 ms 52196 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 28 ms 24412 KB Output is correct
3 Correct 33 ms 24092 KB Output is correct
4 Correct 24 ms 24152 KB Output is correct
5 Correct 23 ms 24220 KB Output is correct
6 Correct 35 ms 24028 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 28 ms 24412 KB Output is correct
3 Correct 33 ms 24092 KB Output is correct
4 Correct 24 ms 24152 KB Output is correct
5 Correct 23 ms 24220 KB Output is correct
6 Correct 35 ms 24028 KB Output is correct
7 Correct 28 ms 23640 KB Output is correct
8 Correct 121 ms 23952 KB Output is correct
9 Correct 447 ms 24148 KB Output is correct
10 Correct 137 ms 24508 KB Output is correct
11 Correct 160 ms 24272 KB Output is correct
12 Correct 2137 ms 24056 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23640 KB Output is correct
2 Correct 609 ms 42440 KB Output is correct
3 Correct 594 ms 42704 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23640 KB Output is correct
2 Correct 609 ms 42440 KB Output is correct
3 Correct 594 ms 42704 KB Output is correct
4 Correct 54 ms 23644 KB Output is correct
5 Correct 1148 ms 42504 KB Output is correct
6 Correct 862 ms 42832 KB Output is correct
7 Correct 2270 ms 42756 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 822 ms 50824 KB Output is correct
3 Correct 816 ms 50904 KB Output is correct
4 Correct 663 ms 52172 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 822 ms 50824 KB Output is correct
3 Correct 816 ms 50904 KB Output is correct
4 Correct 663 ms 52172 KB Output is correct
5 Correct 21 ms 23644 KB Output is correct
6 Correct 943 ms 50636 KB Output is correct
7 Correct 1331 ms 50828 KB Output is correct
8 Correct 1031 ms 50632 KB Output is correct
9 Correct 1018 ms 50660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23644 KB Output is correct
2 Correct 458 ms 42056 KB Output is correct
3 Correct 926 ms 42308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23644 KB Output is correct
2 Correct 458 ms 42056 KB Output is correct
3 Correct 926 ms 42308 KB Output is correct
4 Correct 24 ms 23640 KB Output is correct
5 Correct 1167 ms 41916 KB Output is correct
6 Correct 977 ms 42256 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23640 KB Output is correct
2 Correct 822 ms 50596 KB Output is correct
3 Correct 807 ms 50544 KB Output is correct
4 Correct 688 ms 52196 KB Output is correct
5 Correct 19 ms 23644 KB Output is correct
6 Correct 453 ms 41956 KB Output is correct
7 Correct 843 ms 42200 KB Output is correct
8 Correct 914 ms 43252 KB Output is correct
9 Correct 928 ms 43584 KB Output is correct
10 Correct 1388 ms 45788 KB Output is correct
11 Correct 1414 ms 45172 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23640 KB Output is correct
2 Correct 822 ms 50596 KB Output is correct
3 Correct 807 ms 50544 KB Output is correct
4 Correct 688 ms 52196 KB Output is correct
5 Correct 19 ms 23644 KB Output is correct
6 Correct 453 ms 41956 KB Output is correct
7 Correct 843 ms 42200 KB Output is correct
8 Correct 914 ms 43252 KB Output is correct
9 Correct 928 ms 43584 KB Output is correct
10 Correct 1388 ms 45788 KB Output is correct
11 Correct 1414 ms 45172 KB Output is correct
12 Correct 21 ms 23644 KB Output is correct
13 Correct 937 ms 50260 KB Output is correct
14 Correct 1320 ms 51108 KB Output is correct
15 Correct 1039 ms 50328 KB Output is correct
16 Correct 1024 ms 50408 KB Output is correct
17 Correct 23 ms 23640 KB Output is correct
18 Correct 1167 ms 42292 KB Output is correct
19 Correct 983 ms 42432 KB Output is correct
20 Correct 1020 ms 43160 KB Output is correct
21 Correct 1083 ms 43200 KB Output is correct
22 Correct 2866 ms 44616 KB Output is correct
23 Correct 2108 ms 46740 KB Output is correct
24 Correct 1633 ms 46520 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23588 KB Output is correct
2 Correct 24 ms 23900 KB Output is correct
3 Correct 32 ms 24144 KB Output is correct
4 Correct 24 ms 23892 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 36 ms 23904 KB Output is correct
7 Correct 25 ms 23612 KB Output is correct
8 Correct 617 ms 42692 KB Output is correct
9 Correct 599 ms 42692 KB Output is correct
10 Correct 19 ms 23644 KB Output is correct
11 Correct 840 ms 50828 KB Output is correct
12 Correct 830 ms 50584 KB Output is correct
13 Correct 685 ms 52172 KB Output is correct
14 Correct 19 ms 23644 KB Output is correct
15 Correct 456 ms 42096 KB Output is correct
16 Correct 901 ms 42240 KB Output is correct
17 Correct 929 ms 43380 KB Output is correct
18 Correct 909 ms 43392 KB Output is correct
19 Correct 1364 ms 45556 KB Output is correct
20 Correct 1546 ms 45080 KB Output is correct
21 Correct 626 ms 42596 KB Output is correct
22 Correct 640 ms 42712 KB Output is correct
23 Correct 739 ms 43136 KB Output is correct
24 Correct 702 ms 43172 KB Output is correct
25 Correct 909 ms 44616 KB Output is correct
26 Correct 954 ms 41900 KB Output is correct
27 Correct 930 ms 41960 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23588 KB Output is correct
2 Correct 24 ms 23900 KB Output is correct
3 Correct 32 ms 24144 KB Output is correct
4 Correct 24 ms 23892 KB Output is correct
5 Correct 24 ms 24156 KB Output is correct
6 Correct 36 ms 23904 KB Output is correct
7 Correct 25 ms 23612 KB Output is correct
8 Correct 617 ms 42692 KB Output is correct
9 Correct 599 ms 42692 KB Output is correct
10 Correct 19 ms 23644 KB Output is correct
11 Correct 840 ms 50828 KB Output is correct
12 Correct 830 ms 50584 KB Output is correct
13 Correct 685 ms 52172 KB Output is correct
14 Correct 19 ms 23644 KB Output is correct
15 Correct 456 ms 42096 KB Output is correct
16 Correct 901 ms 42240 KB Output is correct
17 Correct 929 ms 43380 KB Output is correct
18 Correct 909 ms 43392 KB Output is correct
19 Correct 1364 ms 45556 KB Output is correct
20 Correct 1546 ms 45080 KB Output is correct
21 Correct 626 ms 42596 KB Output is correct
22 Correct 640 ms 42712 KB Output is correct
23 Correct 739 ms 43136 KB Output is correct
24 Correct 702 ms 43172 KB Output is correct
25 Correct 909 ms 44616 KB Output is correct
26 Correct 954 ms 41900 KB Output is correct
27 Correct 930 ms 41960 KB Output is correct
28 Correct 28 ms 23644 KB Output is correct
29 Correct 120 ms 23892 KB Output is correct
30 Correct 454 ms 24376 KB Output is correct
31 Correct 133 ms 23892 KB Output is correct
32 Correct 159 ms 24188 KB Output is correct
33 Correct 2139 ms 24252 KB Output is correct
34 Correct 54 ms 23968 KB Output is correct
35 Correct 1171 ms 42820 KB Output is correct
36 Correct 833 ms 43040 KB Output is correct
37 Correct 2279 ms 43092 KB Output is correct
38 Correct 21 ms 23644 KB Output is correct
39 Correct 936 ms 50712 KB Output is correct
40 Correct 1358 ms 50692 KB Output is correct
41 Correct 1022 ms 50420 KB Output is correct
42 Correct 1020 ms 50636 KB Output is correct
43 Correct 24 ms 23644 KB Output is correct
44 Correct 1188 ms 42264 KB Output is correct
45 Correct 991 ms 42128 KB Output is correct
46 Correct 1010 ms 43724 KB Output is correct
47 Correct 1037 ms 43376 KB Output is correct
48 Correct 2697 ms 44776 KB Output is correct
49 Correct 2131 ms 46796 KB Output is correct
50 Correct 1674 ms 46624 KB Output is correct
51 Correct 1519 ms 43012 KB Output is correct
52 Correct 2737 ms 43232 KB Output is correct
53 Correct 2305 ms 45076 KB Output is correct
54 Correct 835 ms 45564 KB Output is correct
55 Correct 2332 ms 45364 KB Output is correct
56 Correct 765 ms 46128 KB Output is correct
57 Correct 1052 ms 47220 KB Output is correct
58 Correct 1136 ms 45100 KB Output is correct
59 Correct 934 ms 45588 KB Output is correct