oj.uz

Submission #865851

# Submission time Handle Problem Language Result Execution time Memory
865851 2023-10-24T23:45:48 Z AbdelmagedNour Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 52564 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[N][3];
int vis[N];
#define dp_down(v) DP[v][0]
#define dp_up(v) DP[v][1]
#define dp(v) DP[v][2]
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);
	for(int i=1;i<=n;i++)dp(i)=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 24412 KB Output is correct
2 Correct 26 ms 24924 KB Output is correct
3 Correct 49 ms 25124 KB Output is correct
4 Correct 26 ms 25076 KB Output is correct
5 Correct 37 ms 25348 KB Output is correct
6 Correct 52 ms 25144 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24412 KB Output is correct
2 Correct 26 ms 24924 KB Output is correct
3 Correct 49 ms 25124 KB Output is correct
4 Correct 26 ms 25076 KB Output is correct
5 Correct 37 ms 25348 KB Output is correct
6 Correct 52 ms 25144 KB Output is correct
7 Correct 29 ms 24224 KB Output is correct
8 Correct 125 ms 24664 KB Output is correct
9 Correct 481 ms 24908 KB Output is correct
10 Correct 145 ms 25140 KB Output is correct
11 Correct 172 ms 24912 KB Output is correct
12 Correct 2198 ms 25360 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24372 KB Output is correct
2 Correct 844 ms 44144 KB Output is correct
3 Correct 577 ms 43716 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24372 KB Output is correct
2 Correct 844 ms 44144 KB Output is correct
3 Correct 577 ms 43716 KB Output is correct
4 Correct 55 ms 24276 KB Output is correct
5 Correct 2013 ms 43856 KB Output is correct
6 Correct 973 ms 43536 KB Output is correct
7 Correct 2504 ms 43388 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24148 KB Output is correct
2 Correct 1014 ms 52480 KB Output is correct
3 Correct 985 ms 52144 KB Output is correct
4 Correct 770 ms 52200 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24148 KB Output is correct
2 Correct 1014 ms 52480 KB Output is correct
3 Correct 985 ms 52144 KB Output is correct
4 Correct 770 ms 52200 KB Output is correct
5 Correct 22 ms 24400 KB Output is correct
6 Correct 1316 ms 51772 KB Output is correct
7 Correct 1371 ms 51892 KB Output is correct
8 Correct 1033 ms 51872 KB Output is correct
9 Correct 1034 ms 51660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24144 KB Output is correct
2 Correct 448 ms 43624 KB Output is correct
3 Correct 849 ms 43756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24144 KB Output is correct
2 Correct 448 ms 43624 KB Output is correct
3 Correct 849 ms 43756 KB Output is correct
4 Correct 25 ms 24156 KB Output is correct
5 Correct 1178 ms 43392 KB Output is correct
6 Correct 995 ms 43392 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24108 KB Output is correct
2 Correct 841 ms 51992 KB Output is correct
3 Correct 871 ms 51944 KB Output is correct
4 Correct 826 ms 51944 KB Output is correct
5 Correct 21 ms 24184 KB Output is correct
6 Correct 487 ms 43500 KB Output is correct
7 Correct 1000 ms 43664 KB Output is correct
8 Correct 883 ms 44892 KB Output is correct
9 Correct 1424 ms 45096 KB Output is correct
10 Correct 2889 ms 47400 KB Output is correct
11 Correct 2211 ms 46688 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24108 KB Output is correct
2 Correct 841 ms 51992 KB Output is correct
3 Correct 871 ms 51944 KB Output is correct
4 Correct 826 ms 51944 KB Output is correct
5 Correct 21 ms 24184 KB Output is correct
6 Correct 487 ms 43500 KB Output is correct
7 Correct 1000 ms 43664 KB Output is correct
8 Correct 883 ms 44892 KB Output is correct
9 Correct 1424 ms 45096 KB Output is correct
10 Correct 2889 ms 47400 KB Output is correct
11 Correct 2211 ms 46688 KB Output is correct
12 Correct 22 ms 24156 KB Output is correct
13 Correct 1114 ms 51712 KB Output is correct
14 Correct 1422 ms 51752 KB Output is correct
15 Correct 1176 ms 51900 KB Output is correct
16 Correct 1084 ms 51660 KB Output is correct
17 Correct 24 ms 24156 KB Output is correct
18 Correct 1215 ms 43344 KB Output is correct
19 Correct 1027 ms 43492 KB Output is correct
20 Correct 1087 ms 44536 KB Output is correct
21 Correct 1465 ms 44856 KB Output is correct
22 Execution timed out 3513 ms 46284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24180 KB Output is correct
2 Correct 27 ms 24916 KB Output is correct
3 Correct 33 ms 25144 KB Output is correct
4 Correct 25 ms 25172 KB Output is correct
5 Correct 25 ms 25436 KB Output is correct
6 Correct 36 ms 25212 KB Output is correct
7 Correct 25 ms 24156 KB Output is correct
8 Correct 634 ms 43956 KB Output is correct
9 Correct 650 ms 43640 KB Output is correct
10 Correct 18 ms 23644 KB Output is correct
11 Correct 870 ms 50068 KB Output is correct
12 Correct 813 ms 50248 KB Output is correct
13 Correct 841 ms 49936 KB Output is correct
14 Correct 23 ms 23636 KB Output is correct
15 Correct 470 ms 41580 KB Output is correct
16 Correct 1331 ms 41636 KB Output is correct
17 Correct 1029 ms 42836 KB Output is correct
18 Correct 1290 ms 42960 KB Output is correct
19 Correct 1939 ms 45116 KB Output is correct
20 Correct 1603 ms 44388 KB Output is correct
21 Correct 524 ms 45004 KB Output is correct
22 Correct 763 ms 45056 KB Output is correct
23 Correct 805 ms 45436 KB Output is correct
24 Correct 803 ms 45524 KB Output is correct
25 Correct 1070 ms 46680 KB Output is correct
26 Correct 1284 ms 44428 KB Output is correct
27 Correct 1182 ms 44660 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24180 KB Output is correct
2 Correct 27 ms 24916 KB Output is correct
3 Correct 33 ms 25144 KB Output is correct
4 Correct 25 ms 25172 KB Output is correct
5 Correct 25 ms 25436 KB Output is correct
6 Correct 36 ms 25212 KB Output is correct
7 Correct 25 ms 24156 KB Output is correct
8 Correct 634 ms 43956 KB Output is correct
9 Correct 650 ms 43640 KB Output is correct
10 Correct 18 ms 23644 KB Output is correct
11 Correct 870 ms 50068 KB Output is correct
12 Correct 813 ms 50248 KB Output is correct
13 Correct 841 ms 49936 KB Output is correct
14 Correct 23 ms 23636 KB Output is correct
15 Correct 470 ms 41580 KB Output is correct
16 Correct 1331 ms 41636 KB Output is correct
17 Correct 1029 ms 42836 KB Output is correct
18 Correct 1290 ms 42960 KB Output is correct
19 Correct 1939 ms 45116 KB Output is correct
20 Correct 1603 ms 44388 KB Output is correct
21 Correct 524 ms 45004 KB Output is correct
22 Correct 763 ms 45056 KB Output is correct
23 Correct 805 ms 45436 KB Output is correct
24 Correct 803 ms 45524 KB Output is correct
25 Correct 1070 ms 46680 KB Output is correct
26 Correct 1284 ms 44428 KB Output is correct
27 Correct 1182 ms 44660 KB Output is correct
28 Correct 30 ms 24400 KB Output is correct
29 Correct 121 ms 25004 KB Output is correct
30 Correct 459 ms 25168 KB Output is correct
31 Correct 136 ms 25160 KB Output is correct
32 Correct 170 ms 25172 KB Output is correct
33 Correct 2155 ms 25284 KB Output is correct
34 Correct 57 ms 24544 KB Output is correct
35 Correct 1539 ms 44320 KB Output is correct
36 Correct 867 ms 43876 KB Output is correct
37 Correct 2323 ms 43920 KB Output is correct
38 Correct 22 ms 24408 KB Output is correct
39 Correct 1105 ms 52368 KB Output is correct
40 Correct 1591 ms 52564 KB Output is correct
41 Correct 1210 ms 52164 KB Output is correct
42 Correct 1182 ms 52368 KB Output is correct
43 Correct 25 ms 24404 KB Output is correct
44 Correct 1190 ms 43956 KB Output is correct
45 Correct 1426 ms 44252 KB Output is correct
46 Correct 1317 ms 45576 KB Output is correct
47 Correct 1496 ms 45532 KB Output is correct
48 Execution timed out 3514 ms 46428 KB Time limit exceeded
49 Halted 0 ms 0 KB -