oj.uz

Submission #428492

# Submission time Handle Problem Language Result Execution time Memory
428492 2021-06-15T12:18:46 Z mosiashvililuka Inside information (BOI21_servers) C++14
50 / 100
 638 ms 36068 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,msh[200009][19],dp[200009],lf[200009],rg[200009],tim,st[200009],shv[200009],dep[200009],f[200009],lc,E,C,D;
int fen1[200009],fen2[200009];
pair <char, pair <int, int> > p[1000009];
vector <int> v[200009];
void upd1(int q, int w){
	while(q<=200001){
		fen1[q]+=w;
		q=q+(q&(-q));
	}
}
int read1(int q){
	int sm=0;
	while(q>=1){
		sm+=fen1[q];
		q=q-(q&(-q));
	}
	return sm;
}
void upd2(int q, int w){
	while(q<=200001){
		fen2[q]+=w;
		q=q+(q&(-q));
	}
}
int read2(int q){
	int sm=0;
	while(q>=1){
		sm+=fen2[q];
		q=q-(q&(-q));
	}
	return sm;
}
bool anc(int q, int w){
	if(lf[q]<=lf[w]&&rg[w]<=rg[q]) return 1; else return 0;
}
int lca(int q, int w){
	if(anc(q,w)) return q;
	if(anc(w,q)) return w;
	for(int h=17; h>=0; h--){
		if(msh[q][h]!=0&&anc(msh[q][h],w)==0){
			q=msh[q][h];
		}
	}
	return msh[q][0];
}
int upto(int q, int w){
	for(int h=17; h>=0; h--){
		if(msh[q][h]!=0&&anc(msh[q][h],w)==0){
			q=msh[q][h];
		}
	}
	return q;
}
void dfsst(int q, int w){
	dep[q]=dep[w]+1;
	msh[q][0]=w;
	for(int h=1; h<=17; h++) msh[q][h]=msh[msh[q][h-1]][h-1];
	//tim++;lf[q]=rg[q]=tim;
	dp[q]=1;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfsst((*it),q);
		dp[q]+=dp[(*it)];
		//if(rg[(*it)]>rg[q]) rg[q]=rg[(*it)];
	}
}
void dfs(int q, int w, bool BO){
	tim++;lf[q]=rg[q]=tim;
	if(BO==0){
		st[q]=q;
	}
	if(q!=1&&v[q].size()==1) return;
	if(v[q].size()==0) return;
	int MX=0;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		if(dp[(*it)]>dp[MX]) MX=(*it);
	}
	shv[q]=MX;st[shv[q]]=st[q];
	dfs(shv[q],q,1);
	if(rg[MX]>rg[q]) rg[q]=rg[MX];
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||(*it)==shv[q]) continue;
		dfs((*it),q,0);
		if(rg[(*it)]>rg[q]) rg[q]=rg[(*it)];
	}
}
void UP1(int q){
	if(anc(q,lc)) return;
	if(f[q]==-1){
		E=1;
		return;
	}
	int w=0;if(lf[st[q]]>lf[lc]) w=st[q]; else w=upto(q,lc);
	if(lf[q]-lf[w]<=0||lf[q]-lf[w]==read1(lf[q]-1)-read1(lf[w]-1)){
		
	}else{
		E=1;
		return;
	}
	if(msh[w][0]!=lc){
		if(f[msh[w][0]]==-1||f[msh[w][0]]>f[w]||f[w]==-1){
			E=1;
			return;
		}
	}
	UP1(msh[w][0]);
}
void UP2(int q){
	if(anc(q,lc)) return;
	if(f[q]==-1){
		E=1;
		return;
	}
	int w=0;if(lf[st[q]]>lf[lc]) w=st[q]; else w=upto(q,lc);
	//if(lf[q]-lf[w]==read2(lf[q])-read2(lf[w]-1)){
	if(lf[q]-lf[w]<=0||lf[q]-lf[w]==read2(lf[q]-1)-read2(lf[w]-1)){
		
	}else{
		E=1;
		return;
	}
	if(msh[w][0]!=lc){
		if(f[msh[w][0]]==-1||f[msh[w][0]]<f[w]||f[w]==-1){
			E=1;
			return;
		}
	}
	UP2(msh[w][0]);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	tes=tes+a-1;
	for(t=1; t<=tes; t++){
		cin>>p[t].first;
		if(p[t].first=='S'){
			cin>>p[t].second.first>>p[t].second.second;
			v[p[t].second.first].push_back(p[t].second.second);
			v[p[t].second.second].push_back(p[t].second.first);
		}
		if(p[t].first=='Q'){
			cin>>p[t].second.first>>p[t].second.second;
		}
		if(p[t].first=='C'){
			cin>>p[t].second.first;
		}
	}
	dfsst(1,0);
	dfs(1,0,0);
	for(i=1; i<=a; i++) f[i]=-1;
	/*for(i=1; i<=a; i++){
		cout<<lf[i]<<" "<<shv[i]<<" "<<st[i]<<endl;
	}*/
	for(t=1; t<=tes; t++){
		if(p[t].first=='S'){
			c=p[t].second.first;d=p[t].second.second;
			if(msh[c][0]==d) swap(c,d);
			f[d]=t;
			if(shv[d]!=0){
				if(f[shv[d]]!=-1){
					upd2(lf[d],1);
				}
			}
			if(st[d]!=d){
				if(f[c]!=-1){
					upd1(lf[c],1);
				}
			}
			continue;
		}
		if(p[t].first=='Q'){
			//cout<<read1(3)<<" "<<read1(1)<<endl;
			//return 0;
			d=p[t].second.first;c=p[t].second.second;
			E=0;
			lc=lca(c,d);
			UP1(d);UP2(c);
			if(c!=lc&&d!=lc){
				C=upto(c,lc);D=upto(d,lc);
				if(f[C]==-1||f[D]==-1||f[C]>f[D]) E=1;
			}
			if(E==0){
				cout<<"yes"<<endl;
			}else{
				cout<<"no"<<endl;
			}
			//return 0;
			continue;
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 247 ms 6884 KB Output is correct
2 Correct 250 ms 8824 KB Output is correct
3 Correct 237 ms 8900 KB Output is correct
4 Correct 273 ms 8872 KB Output is correct
5 Correct 268 ms 9072 KB Output is correct
6 Correct 235 ms 8832 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 247 ms 6884 KB Output is correct
2 Correct 250 ms 8824 KB Output is correct
3 Correct 237 ms 8900 KB Output is correct
4 Correct 273 ms 8872 KB Output is correct
5 Correct 268 ms 9072 KB Output is correct
6 Correct 235 ms 8832 KB Output is correct
7 Incorrect 215 ms 7672 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 225 ms 6828 KB Output is correct
2 Correct 395 ms 24156 KB Output is correct
3 Correct 371 ms 24172 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 225 ms 6828 KB Output is correct
2 Correct 395 ms 24156 KB Output is correct
3 Correct 371 ms 24172 KB Output is correct
4 Incorrect 222 ms 6780 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 229 ms 6880 KB Output is correct
2 Correct 455 ms 32704 KB Output is correct
3 Correct 471 ms 32680 KB Output is correct
4 Correct 433 ms 32188 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 6880 KB Output is correct
2 Correct 455 ms 32704 KB Output is correct
3 Correct 471 ms 32680 KB Output is correct
4 Correct 433 ms 32188 KB Output is correct
5 Incorrect 210 ms 6800 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 226 ms 6792 KB Output is correct
2 Correct 387 ms 27724 KB Output is correct
3 Correct 428 ms 28284 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 6792 KB Output is correct
2 Correct 387 ms 27724 KB Output is correct
3 Correct 428 ms 28284 KB Output is correct
4 Incorrect 224 ms 7696 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 218 ms 6876 KB Output is correct
2 Correct 436 ms 32692 KB Output is correct
3 Correct 513 ms 32688 KB Output is correct
4 Correct 454 ms 32156 KB Output is correct
5 Correct 231 ms 6844 KB Output is correct
6 Correct 396 ms 27708 KB Output is correct
7 Correct 410 ms 28232 KB Output is correct
8 Correct 520 ms 28732 KB Output is correct
9 Correct 461 ms 28680 KB Output is correct
10 Correct 450 ms 30664 KB Output is correct
11 Correct 576 ms 30160 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 218 ms 6876 KB Output is correct
2 Correct 436 ms 32692 KB Output is correct
3 Correct 513 ms 32688 KB Output is correct
4 Correct 454 ms 32156 KB Output is correct
5 Correct 231 ms 6844 KB Output is correct
6 Correct 396 ms 27708 KB Output is correct
7 Correct 410 ms 28232 KB Output is correct
8 Correct 520 ms 28732 KB Output is correct
9 Correct 461 ms 28680 KB Output is correct
10 Correct 450 ms 30664 KB Output is correct
11 Correct 576 ms 30160 KB Output is correct
12 Incorrect 254 ms 7652 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 226 ms 6896 KB Output is correct
2 Correct 282 ms 9072 KB Output is correct
3 Correct 255 ms 8876 KB Output is correct
4 Correct 276 ms 8880 KB Output is correct
5 Correct 340 ms 9052 KB Output is correct
6 Correct 255 ms 8924 KB Output is correct
7 Correct 224 ms 7748 KB Output is correct
8 Correct 358 ms 27068 KB Output is correct
9 Correct 443 ms 27048 KB Output is correct
10 Correct 250 ms 7792 KB Output is correct
11 Correct 415 ms 36068 KB Output is correct
12 Correct 440 ms 36064 KB Output is correct
13 Correct 638 ms 35508 KB Output is correct
14 Correct 249 ms 7780 KB Output is correct
15 Correct 408 ms 27704 KB Output is correct
16 Correct 424 ms 28220 KB Output is correct
17 Correct 478 ms 28648 KB Output is correct
18 Correct 465 ms 28784 KB Output is correct
19 Correct 450 ms 30644 KB Output is correct
20 Correct 559 ms 30088 KB Output is correct
21 Correct 372 ms 27688 KB Output is correct
22 Correct 462 ms 27820 KB Output is correct
23 Correct 416 ms 28496 KB Output is correct
24 Correct 412 ms 28584 KB Output is correct
25 Correct 479 ms 30396 KB Output is correct
26 Correct 421 ms 28804 KB Output is correct
27 Correct 374 ms 28740 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 226 ms 6896 KB Output is correct
2 Correct 282 ms 9072 KB Output is correct
3 Correct 255 ms 8876 KB Output is correct
4 Correct 276 ms 8880 KB Output is correct
5 Correct 340 ms 9052 KB Output is correct
6 Correct 255 ms 8924 KB Output is correct
7 Correct 224 ms 7748 KB Output is correct
8 Correct 358 ms 27068 KB Output is correct
9 Correct 443 ms 27048 KB Output is correct
10 Correct 250 ms 7792 KB Output is correct
11 Correct 415 ms 36068 KB Output is correct
12 Correct 440 ms 36064 KB Output is correct
13 Correct 638 ms 35508 KB Output is correct
14 Correct 249 ms 7780 KB Output is correct
15 Correct 408 ms 27704 KB Output is correct
16 Correct 424 ms 28220 KB Output is correct
17 Correct 478 ms 28648 KB Output is correct
18 Correct 465 ms 28784 KB Output is correct
19 Correct 450 ms 30644 KB Output is correct
20 Correct 559 ms 30088 KB Output is correct
21 Correct 372 ms 27688 KB Output is correct
22 Correct 462 ms 27820 KB Output is correct
23 Correct 416 ms 28496 KB Output is correct
24 Correct 412 ms 28584 KB Output is correct
25 Correct 479 ms 30396 KB Output is correct
26 Correct 421 ms 28804 KB Output is correct
27 Correct 374 ms 28740 KB Output is correct
28 Incorrect 219 ms 7744 KB Extra information in the output file
29 Halted 0 ms 0 KB -