oj.uz

Submission #865836

# Submission time Handle Problem Language Result Execution time Memory
865836 2023-10-24T23:13:45 Z AbdelmagedNour Inside information (BOI21_servers) C++17
2.5 / 100
 3500 ms 209736 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);
	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]);
			reclac();
		}else if(op[i]=='Q')cout<<(can_reach(B[i],A[i],i)?"yes\n":"no\n");
		else cout<<dp[A[i]]<<"\n";
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184916 KB Output is correct
2 Correct 580 ms 187296 KB Output is correct
3 Correct 406 ms 187408 KB Output is correct
4 Correct 534 ms 187476 KB Output is correct
5 Correct 522 ms 187588 KB Output is correct
6 Correct 416 ms 187336 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 105 ms 184916 KB Output is correct
2 Correct 580 ms 187296 KB Output is correct
3 Correct 406 ms 187408 KB Output is correct
4 Correct 534 ms 187476 KB Output is correct
5 Correct 522 ms 187588 KB Output is correct
6 Correct 416 ms 187336 KB Output is correct
7 Incorrect 104 ms 182864 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 184912 KB Output is correct
2 Execution timed out 3581 ms 200948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 184912 KB Output is correct
2 Execution timed out 3581 ms 200948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 184888 KB Output is correct
2 Execution timed out 3564 ms 209376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 184888 KB Output is correct
2 Execution timed out 3564 ms 209376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184916 KB Output is correct
2 Execution timed out 3559 ms 202580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 184916 KB Output is correct
2 Execution timed out 3559 ms 202580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 101 ms 184916 KB Output is correct
2 Execution timed out 3594 ms 209736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 101 ms 184916 KB Output is correct
2 Execution timed out 3594 ms 209736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 184976 KB Output is correct
2 Correct 580 ms 187296 KB Output is correct
3 Correct 396 ms 187212 KB Output is correct
4 Correct 543 ms 187468 KB Output is correct
5 Correct 469 ms 188136 KB Output is correct
6 Correct 412 ms 187264 KB Output is correct
7 Correct 120 ms 185120 KB Output is correct
8 Execution timed out 3579 ms 201272 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 184976 KB Output is correct
2 Correct 580 ms 187296 KB Output is correct
3 Correct 396 ms 187212 KB Output is correct
4 Correct 543 ms 187468 KB Output is correct
5 Correct 469 ms 188136 KB Output is correct
6 Correct 412 ms 187264 KB Output is correct
7 Correct 120 ms 185120 KB Output is correct
8 Execution timed out 3579 ms 201272 KB Time limit exceeded
9 Halted 0 ms 0 KB -