oj.uz

Submission #404742

# Submission time Handle Problem Language Result Execution time Memory
404742 2021-05-14T22:30:07 Z AmineWeslati Inside information (BOI21_servers) C++14
0 / 100
 288 ms 20964 KB 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size();

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void IO(){
#ifdef LOCAL
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
}

//-----------------------------------------

const int MX=240000+500;
const int LOG=20;
int N,Q,ty[MX],U[MX],V[MX];

int jump[MX][LOG],jump_max[MX][LOG],jump_inc[MX],jump_dec[MX];
int in[MX],out[MX],cnt=0,par[MX];
unordered_map<int,int>ed[MX];
vi adj[MX];

void build(){
	ed[1][1]=0;
	FOR(i,0,Q) if(!ty[i]){
		int u=U[i],v=V[i];
		ed[u][v]=ed[v][u]=i;
		adj[u].pb(v); 
		adj[v].pb(u);
	}
}
void dfs(int u, int p){
	in[u]=++cnt; 
	par[u]=p;

	jump_inc[u]=p;
	jump_dec[u]=p;
	if(p!=1){
		if(ed[p][par[p]]>ed[u][p]) jump_inc[u]=jump_inc[p];
		else jump_dec[u]=jump_dec[p];
	}
	
	jump[u][0]=p;
	jump_max[u][0]=ed[u][p];
	FOR(i,1,LOG){
		jump[u][i]=jump[jump[u][i-1]][i-1];
		jump_max[u][i]=max(jump_max[u][i-1],
			jump_max[jump[u][i-1]][i-1]);
	}

	for(int v: adj[u]) if(v!=p) dfs(v,u);

	out[u]=++cnt; 
}
void precompute(){
	build();
	dfs(1,1);
}

bool ancestor(int u, int v){
	return in[u]<=in[v] && out[u]>=out[v];
}

int main(){
	IO();

	cin>>N>>Q; Q+=N-1;
	FOR(i,0,Q){
		char c; cin>>c;
		if(c=='S') ty[i]=0;
		else ty[i]=1;

		cin>>U[i]>>V[i];
	}


	precompute();

	FOR(idx,0,Q) if(ty[idx]){
		int u=V[idx],v=U[idx];
		int init_u=u,init_v=v; 

		ROF(i,0,LOG) 
			if(!ancestor(jump[u][i],init_v) && jump_max[u][i]<=idx)
				u=jump[u][i];

		ROF(i,0,LOG)
			if(!ancestor(jump[v][i],init_u) && jump_max[v][i]<=idx)
				v=jump[v][i];

		bool smooth=1;
		if(!ancestor(u,init_v)){
			if(jump_max[u][0]>idx) smooth=0;
		}
		if(!ancestor(v,init_u)){
			if(jump_max[v][0]>idx) smooth=0;
		}
		if(!ancestor(u,init_v) && !ancestor(u,init_v)){
			if(jump_max[u][0]>jump_max[v][0]) smooth=0;
		}
		if(!ancestor(u,init_v)){
			u=jump[u][0];
		}
		if(!ancestor(v,init_u)){
			v=jump[v][0];
		}

		if(ancestor(u,jump_inc[init_u]))
			u=jump_inc[init_u];
		if(ancestor(v,jump_dec[init_v]))
			v=jump_dec[init_v];

		if(smooth && ancestor(u,init_v) && ancestor(v,init_u)) 
			cout << "yes" << endl;
		else cout << "no" << endl;
	}

}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 20964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 20964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 20960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 20960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 20936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 20936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 20936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 20936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 269 ms 20932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 269 ms 20932 KB Output isn't correct
2 Halted 0 ms 0 KB -