oj.uz

Submission #865837

# Submission time Handle Problem Language Result Execution time Memory
865837 2023-10-24T23:14:38 Z AbdelmagedNour Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 269328 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=250005;
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);
	bool flag=0;
	for(int i=1;i<n+q;i++){
		if(op[i]=='S'){
			cur_adj[A[i]].push_front(B[i]);
			cur_adj[B[i]].push_front(A[i]);
			flag=0;
		}else if(op[i]=='Q')cout<<(can_reach(B[i],A[i],i)?"yes\n":"no\n");
		else {
			if(!flag)flag=1,reclac();
			cout<<dp[A[i]]<<"\n";
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 183260 KB Output is correct
2 Correct 115 ms 185428 KB Output is correct
3 Correct 119 ms 185168 KB Output is correct
4 Correct 110 ms 185292 KB Output is correct
5 Correct 109 ms 185328 KB Output is correct
6 Correct 126 ms 185172 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 183260 KB Output is correct
2 Correct 115 ms 185428 KB Output is correct
3 Correct 119 ms 185168 KB Output is correct
4 Correct 110 ms 185292 KB Output is correct
5 Correct 109 ms 185328 KB Output is correct
6 Correct 126 ms 185172 KB Output is correct
7 Correct 105 ms 185092 KB Output is correct
8 Correct 533 ms 188448 KB Output is correct
9 Correct 248 ms 188500 KB Output is correct
10 Correct 514 ms 188548 KB Output is correct
11 Correct 296 ms 188500 KB Output is correct
12 Correct 410 ms 188648 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 183068 KB Output is correct
2 Correct 253 ms 259780 KB Output is correct
3 Correct 251 ms 262596 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 183068 KB Output is correct
2 Correct 253 ms 259780 KB Output is correct
3 Correct 251 ms 262596 KB Output is correct
4 Correct 115 ms 185784 KB Output is correct
5 Execution timed out 3602 ms 207488 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 182916 KB Output is correct
2 Correct 256 ms 266308 KB Output is correct
3 Correct 242 ms 269328 KB Output is correct
4 Correct 239 ms 269136 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 182916 KB Output is correct
2 Correct 256 ms 266308 KB Output is correct
3 Correct 242 ms 269328 KB Output is correct
4 Correct 239 ms 269136 KB Output is correct
5 Correct 104 ms 185932 KB Output is correct
6 Execution timed out 3563 ms 215256 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 182864 KB Output is correct
2 Correct 224 ms 259156 KB Output is correct
3 Correct 254 ms 262992 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 182864 KB Output is correct
2 Correct 224 ms 259156 KB Output is correct
3 Correct 254 ms 262992 KB Output is correct
4 Correct 103 ms 185704 KB Output is correct
5 Execution timed out 3534 ms 211196 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 183016 KB Output is correct
2 Correct 245 ms 265812 KB Output is correct
3 Correct 256 ms 269128 KB Output is correct
4 Correct 247 ms 269208 KB Output is correct
5 Correct 105 ms 183892 KB Output is correct
6 Correct 235 ms 262448 KB Output is correct
7 Correct 250 ms 263056 KB Output is correct
8 Correct 257 ms 263572 KB Output is correct
9 Correct 262 ms 263592 KB Output is correct
10 Correct 265 ms 267344 KB Output is correct
11 Correct 274 ms 267024 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 183016 KB Output is correct
2 Correct 245 ms 265812 KB Output is correct
3 Correct 256 ms 269128 KB Output is correct
4 Correct 247 ms 269208 KB Output is correct
5 Correct 105 ms 183892 KB Output is correct
6 Correct 235 ms 262448 KB Output is correct
7 Correct 250 ms 263056 KB Output is correct
8 Correct 257 ms 263572 KB Output is correct
9 Correct 262 ms 263592 KB Output is correct
10 Correct 265 ms 267344 KB Output is correct
11 Correct 274 ms 267024 KB Output is correct
12 Correct 103 ms 185940 KB Output is correct
13 Execution timed out 3568 ms 215144 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 183808 KB Output is correct
2 Correct 108 ms 186316 KB Output is correct
3 Correct 121 ms 186196 KB Output is correct
4 Correct 115 ms 186532 KB Output is correct
5 Correct 111 ms 186452 KB Output is correct
6 Correct 123 ms 186400 KB Output is correct
7 Correct 116 ms 183832 KB Output is correct
8 Correct 262 ms 261832 KB Output is correct
9 Correct 248 ms 262596 KB Output is correct
10 Correct 102 ms 183888 KB Output is correct
11 Correct 244 ms 269136 KB Output is correct
12 Correct 253 ms 269248 KB Output is correct
13 Correct 250 ms 269144 KB Output is correct
14 Correct 105 ms 183936 KB Output is correct
15 Correct 223 ms 262480 KB Output is correct
16 Correct 250 ms 263036 KB Output is correct
17 Correct 242 ms 263508 KB Output is correct
18 Correct 270 ms 263724 KB Output is correct
19 Correct 260 ms 267348 KB Output is correct
20 Correct 275 ms 267016 KB Output is correct
21 Correct 259 ms 263292 KB Output is correct
22 Correct 296 ms 263252 KB Output is correct
23 Correct 265 ms 263476 KB Output is correct
24 Correct 259 ms 263328 KB Output is correct
25 Correct 281 ms 264460 KB Output is correct
26 Correct 246 ms 262740 KB Output is correct
27 Correct 236 ms 262484 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 183808 KB Output is correct
2 Correct 108 ms 186316 KB Output is correct
3 Correct 121 ms 186196 KB Output is correct
4 Correct 115 ms 186532 KB Output is correct
5 Correct 111 ms 186452 KB Output is correct
6 Correct 123 ms 186400 KB Output is correct
7 Correct 116 ms 183832 KB Output is correct
8 Correct 262 ms 261832 KB Output is correct
9 Correct 248 ms 262596 KB Output is correct
10 Correct 102 ms 183888 KB Output is correct
11 Correct 244 ms 269136 KB Output is correct
12 Correct 253 ms 269248 KB Output is correct
13 Correct 250 ms 269144 KB Output is correct
14 Correct 105 ms 183936 KB Output is correct
15 Correct 223 ms 262480 KB Output is correct
16 Correct 250 ms 263036 KB Output is correct
17 Correct 242 ms 263508 KB Output is correct
18 Correct 270 ms 263724 KB Output is correct
19 Correct 260 ms 267348 KB Output is correct
20 Correct 275 ms 267016 KB Output is correct
21 Correct 259 ms 263292 KB Output is correct
22 Correct 296 ms 263252 KB Output is correct
23 Correct 265 ms 263476 KB Output is correct
24 Correct 259 ms 263328 KB Output is correct
25 Correct 281 ms 264460 KB Output is correct
26 Correct 246 ms 262740 KB Output is correct
27 Correct 236 ms 262484 KB Output is correct
28 Correct 106 ms 185936 KB Output is correct
29 Correct 534 ms 188396 KB Output is correct
30 Correct 259 ms 188500 KB Output is correct
31 Correct 518 ms 188624 KB Output is correct
32 Correct 295 ms 188656 KB Output is correct
33 Correct 390 ms 188500 KB Output is correct
34 Correct 120 ms 185940 KB Output is correct
35 Execution timed out 3560 ms 206636 KB Time limit exceeded
36 Halted 0 ms 0 KB -