oj.uz

Submission #890738

# Submission time Handle Problem Language Result Execution time Memory
890738 2023-12-21T20:51:36 Z amirhoseinfar1385 Jail (JOI22_jail) C++17
0 / 100
 39 ms 65640 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=120000+10,maxl=18;
vector<int>adj[maxn];
int res=1,n,m,timea=0,sz[maxn],alln[maxn],lca[maxl][maxn],ted[maxn],high[maxn],parh[maxn],vas[maxn];
pair<int,int>allq[maxn],stf[maxn];
int dfs(int u);
int kaf=(1<<18);

struct segment{
	set<int>st[(1<<19)];
	vector<int>v;
	void clear(){
		for(auto x:v){
			st[x].clear();
		}
		v.clear();
	}
	void add(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			v.push_back(i);
			st[i].insert(w);
			return ;
		}
		int m=(l+r)>>1;
		add((i<<1),l,m,tl,tr,w);
		add((i<<1)^1,m+1,r,tl,tr,w);
		return ;	
	}
	void pors(int i,int w){
		if(i==0){
			return ;
		}
		int now=0;
		while(true){
			if((int)st[i].size()==0||(*st[i].rbegin())<=now){
				break;
			}
			auto x=*st[i].upper_bound(now);
			if(x==w){
				now=x;
				continue;
			}
			if(dfs(x)){
				st[i].erase(x);
			}
			now=x;
		}
		pors((i>>1),w);
	}
}seg;

struct segmentn{
	set<int>st[(1<<19)];
	vector<int>v;
	void clear(){
		for(auto x:v){
			st[x].clear();
		}
		v.clear();
	}
	void add(int i,int w){
		if(i==0){
			return ;
		}
		v.push_back(i);
		st[i].insert(w);
		return add(i>>1,w);
	}
	void pors(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			int now=0;
			while(true){
				//cout<<"chy: "<<l<<" "<<r<<" "<<now<<" "<<(int)st[i].size()<<endl;
				if((int)st[i].size()==0||(*st[i].rbegin())<=now){
					break;
				}
				auto x=*st[i].upper_bound(now);
				//cout<<"aha: "<<i<<" "<<l<<" "<<r<<" "<<x<<endl;
				if(x==w){
					//st[i].erase(x);
					now=x;
					continue;
				}
				if(dfs(x)){
					//cout<<"nago: "<<i<<" "<<l<<" "<<r<<" "<<x<<endl;
					st[i].erase(x);
				}
				now=x;
			}	
			return ;
		}
		int m=(l+r)>>1;
		pors((i<<1),l,m,tl,tr,w);
		pors((i<<1)^1,m+1,r,tl,tr,w);
	}
}segn;

bool cmp(int a,int b){
	return sz[a]>sz[b];
}

int zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=maxl-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

void callca(){
	for(int i=1;i<maxl;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

void dfs1(int u=1,int par=0){
	lca[0][u]=par;
	sz[u]=1;
	for(auto x:adj[u]){
		if(x!=par){
			high[x]=high[u]+1;
			dfs1(x,u);
			sz[u]+=sz[x];
		}
	}
	if(u!=1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
}

void dfs2(int u=1,int par=1){
	parh[u]=par;
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		dfs2(x,x==adj[u][0]?par:x);
	}
	stf[u].second=timea;
}

void vorod(){
	segn.clear();
	seg.clear();
	timea=0;
	memset(vas,0,sizeof(vas));
	memset(ted,0,sizeof(ted));
	cin>>n;
	for(int i=1;i<=n;i++){
		adj[i].clear();
		alln[i]=-1;
	}
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		ted[i]=0;
		cin>>allq[i].first>>allq[i].second;
		alln[allq[i].first]=i;
		alln[allq[i].second]=i;
	}	
}

int dis(int u,int v){
	int uv=getlca(u,v);
	return high[u]+high[v]-2*high[uv];
}

int din(int uv,int u,int v){
	int a=dis(u,v),b=dis(uv,u),c=dis(uv,v);
	if(b+c==a){
		return 1;
	}
	return 0;
}

void go(int u,int had,int ind){
	////cout<<"in: "<<u<<" "<<had<<" "<<ind<<" "<<parh[u]<<" "<<lca[0][parh[u]]<<endl;
	if(zird(had,parh[u])){
		seg.add(1,0,kaf-1,stf[had].first+1,stf[u].first,ind);
		return ;
	}
	go(lca[0][parh[u]],had,ind);
	seg.add(1,0,kaf-1,stf[parh[u]].first,stf[u].first,ind);
}

void add(int u,int v,int ind){
	int uv=getlca(u,v);
	go(u,uv,ind);
	go(v,uv,ind);
	seg.add(1,0,kaf-1,stf[uv].first,stf[uv].first,ind);
}

void addn(int u,int ind){
	segn.add(stf[u].first+kaf,ind);
}

void gop(int u,int had,int ind){
	//cout<<"tof: "<<u<<" "<<had<<" "<<ind<<" "<<parh[u]<<" "<<stf[u].first<<" "<<stf[had].first<<" "<<stf[parh[u]].first<<endl;
	if(zird(had,parh[u])){
		segn.pors(1,0,kaf-1,stf[had].first,stf[u].first,ind);
		return ;
	}
	gop(lca[0][parh[u]],had,ind);
	segn.pors(1,0,kaf-1,stf[parh[u]].first,stf[u].first,ind);
}

void pors(int u,int v,int ind){
	int uv=getlca(u,v);
	gop(u,uv,ind);
	gop(v,uv,ind);
}

int dfs(int u){
	//cout<<"ins: "<<u<<endl;
	if(vas[u]==1){
		res=0;
		return 1;
	}
	if(vas[u]==2){
		return 1;
	}
	vas[u]=1;
	seg.pors(stf[allq[u].second].first+1,u);
	pors(allq[u].first,allq[u].second,u);
	vas[u]=2;
	//cout<<"out: "<<u<<endl;
	return 0;
}

void solve(){
	for(int i=1;i<=m;i++){
//		//cout<<"wtf "<<i<<endl;
		add(allq[i].first,allq[i].second,i);
//		//cout<<i<<endl;
		addn(allq[i].first,i);
//		//cout<<"by: "<<i<<endl;
	}
	////cout<<"salam"<<endl;
	res=1;
	for(int i=1;i<=m;i++){
		dfs(i);
	}
	if(res){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}
}	

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	int t;
	cin>>t;
	for(int asd=0;asd<t;asd++){
		vorod();
		dfs1();
		dfs2();
		callca();
		solve();		
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65628 KB Output is correct
2 Correct 13 ms 65628 KB Output is correct
3 Correct 14 ms 65628 KB Output is correct
4 Incorrect 28 ms 65628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65624 KB Output is correct
2 Correct 12 ms 65628 KB Output is correct
3 Incorrect 14 ms 65628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65624 KB Output is correct
2 Correct 12 ms 65628 KB Output is correct
3 Incorrect 14 ms 65628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65624 KB Output is correct
2 Correct 12 ms 65628 KB Output is correct
3 Incorrect 14 ms 65628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65624 KB Output is correct
2 Correct 12 ms 65628 KB Output is correct
3 Incorrect 14 ms 65628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65624 KB Output is correct
2 Correct 13 ms 65580 KB Output is correct
3 Correct 12 ms 65640 KB Output is correct
4 Correct 12 ms 65624 KB Output is correct
5 Incorrect 39 ms 65628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65628 KB Output is correct
2 Correct 13 ms 65628 KB Output is correct
3 Correct 14 ms 65628 KB Output is correct
4 Incorrect 28 ms 65628 KB Output isn't correct
5 Halted 0 ms 0 KB -