oj.uz

Submission #404747

# Submission time Handle Problem Language Result Execution time Memory
404747 2021-05-14T22:42:55 Z AmineWeslati Inside information (BOI21_servers) C++14
50 / 100
 747 ms 81196 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;

unordered_map<int,int>ed[MX];
vi adj[MX],par(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]; //u-->v
		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) && !ancestor(v,init_u))
			if(jump_max[u][0]>jump_max[v][0]) smooth=0;

		if(!ancestor(u,init_v) && jump_max[u][0]<=idx)
			u=jump[u][0];
		
		if(!ancestor(v,init_u) && jump_max[v][0]<=idx)
			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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 271 ms 21832 KB Output is correct
2 Correct 303 ms 24928 KB Output is correct
3 Correct 300 ms 24900 KB Output is correct
4 Correct 307 ms 24880 KB Output is correct
5 Correct 315 ms 25080 KB Output is correct
6 Correct 306 ms 24876 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 271 ms 21832 KB Output is correct
2 Correct 303 ms 24928 KB Output is correct
3 Correct 300 ms 24900 KB Output is correct
4 Correct 307 ms 24880 KB Output is correct
5 Correct 315 ms 25080 KB Output is correct
6 Correct 306 ms 24876 KB Output is correct
7 Incorrect 227 ms 21084 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 269 ms 22020 KB Output is correct
2 Correct 596 ms 72972 KB Output is correct
3 Correct 600 ms 73188 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 269 ms 22020 KB Output is correct
2 Correct 596 ms 72972 KB Output is correct
3 Correct 600 ms 73188 KB Output is correct
4 Incorrect 213 ms 21172 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 21792 KB Output is correct
2 Correct 642 ms 81196 KB Output is correct
3 Correct 632 ms 81100 KB Output is correct
4 Correct 581 ms 81152 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 21792 KB Output is correct
2 Correct 642 ms 81196 KB Output is correct
3 Correct 632 ms 81100 KB Output is correct
4 Correct 581 ms 81152 KB Output is correct
5 Incorrect 214 ms 21176 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21960 KB Output is correct
2 Correct 541 ms 71684 KB Output is correct
3 Correct 702 ms 71696 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21960 KB Output is correct
2 Correct 541 ms 71684 KB Output is correct
3 Correct 702 ms 71696 KB Output is correct
4 Incorrect 219 ms 21124 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 269 ms 21864 KB Output is correct
2 Correct 651 ms 81176 KB Output is correct
3 Correct 645 ms 81032 KB Output is correct
4 Correct 572 ms 81056 KB Output is correct
5 Correct 273 ms 22688 KB Output is correct
6 Correct 527 ms 71640 KB Output is correct
7 Correct 650 ms 71708 KB Output is correct
8 Correct 720 ms 72156 KB Output is correct
9 Correct 661 ms 72172 KB Output is correct
10 Correct 660 ms 75268 KB Output is correct
11 Correct 709 ms 74624 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 269 ms 21864 KB Output is correct
2 Correct 651 ms 81176 KB Output is correct
3 Correct 645 ms 81032 KB Output is correct
4 Correct 572 ms 81056 KB Output is correct
5 Correct 273 ms 22688 KB Output is correct
6 Correct 527 ms 71640 KB Output is correct
7 Correct 650 ms 71708 KB Output is correct
8 Correct 720 ms 72156 KB Output is correct
9 Correct 661 ms 72172 KB Output is correct
10 Correct 660 ms 75268 KB Output is correct
11 Correct 709 ms 74624 KB Output is correct
12 Incorrect 217 ms 21168 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21904 KB Output is correct
2 Correct 301 ms 24788 KB Output is correct
3 Correct 292 ms 24948 KB Output is correct
4 Correct 313 ms 24952 KB Output is correct
5 Correct 313 ms 25036 KB Output is correct
6 Correct 295 ms 25044 KB Output is correct
7 Correct 276 ms 22796 KB Output is correct
8 Correct 572 ms 72968 KB Output is correct
9 Correct 600 ms 73192 KB Output is correct
10 Correct 270 ms 22816 KB Output is correct
11 Correct 640 ms 81032 KB Output is correct
12 Correct 674 ms 81104 KB Output is correct
13 Correct 597 ms 81096 KB Output is correct
14 Correct 274 ms 22772 KB Output is correct
15 Correct 562 ms 71620 KB Output is correct
16 Correct 643 ms 71744 KB Output is correct
17 Correct 702 ms 72152 KB Output is correct
18 Correct 674 ms 72136 KB Output is correct
19 Correct 655 ms 75252 KB Output is correct
20 Correct 747 ms 74476 KB Output is correct
21 Correct 622 ms 73564 KB Output is correct
22 Correct 642 ms 73248 KB Output is correct
23 Correct 709 ms 73776 KB Output is correct
24 Correct 642 ms 73868 KB Output is correct
25 Correct 686 ms 75300 KB Output is correct
26 Correct 635 ms 71960 KB Output is correct
27 Correct 617 ms 71964 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21904 KB Output is correct
2 Correct 301 ms 24788 KB Output is correct
3 Correct 292 ms 24948 KB Output is correct
4 Correct 313 ms 24952 KB Output is correct
5 Correct 313 ms 25036 KB Output is correct
6 Correct 295 ms 25044 KB Output is correct
7 Correct 276 ms 22796 KB Output is correct
8 Correct 572 ms 72968 KB Output is correct
9 Correct 600 ms 73192 KB Output is correct
10 Correct 270 ms 22816 KB Output is correct
11 Correct 640 ms 81032 KB Output is correct
12 Correct 674 ms 81104 KB Output is correct
13 Correct 597 ms 81096 KB Output is correct
14 Correct 274 ms 22772 KB Output is correct
15 Correct 562 ms 71620 KB Output is correct
16 Correct 643 ms 71744 KB Output is correct
17 Correct 702 ms 72152 KB Output is correct
18 Correct 674 ms 72136 KB Output is correct
19 Correct 655 ms 75252 KB Output is correct
20 Correct 747 ms 74476 KB Output is correct
21 Correct 622 ms 73564 KB Output is correct
22 Correct 642 ms 73248 KB Output is correct
23 Correct 709 ms 73776 KB Output is correct
24 Correct 642 ms 73868 KB Output is correct
25 Correct 686 ms 75300 KB Output is correct
26 Correct 635 ms 71960 KB Output is correct
27 Correct 617 ms 71964 KB Output is correct
28 Incorrect 220 ms 21156 KB Extra information in the output file
29 Halted 0 ms 0 KB -