Submission #428465

#	Time	Username	Problem	Language	Result	Execution time	Memory
428465		mosiashvililuka	Inside information (BOI21_servers)	C++14	7.50 / 100	433 ms	36164 KiB

servers

#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,lf[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,lf[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: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5