Submission #1242228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242228		hamanp87	Jail (JOI22_jail)	C++20	0 / 100	15 ms	3144 KiB

jail

#include<bits/stdc++.h>
using namespace std;

typedef vector<int> veci;

const int N=12e4+5;
int n,m,q,pars[N][18],dep[N],up[N],dn[N];
veci adj[N];
bool bad;

void dfs0(int u,int p)
{
	pars[u][0]=p;
	dep[u]=(p<0?0:dep[p]+1);
	for(int v:adj[u])
	{
		if(v==p)
			continue;
		dfs0(v,u);
	}
}

int LCA(int a,int b)
{
	if(dep[a]<dep[b])
		swap(a,b);
	
	int dif=dep[a]-dep[b];
	for(int k=0;k<18;k++)
		if(dif&(1<<k))
			a=pars[a][k];
	
	if(a==b)
		return a;
	
	for(int k=17;k>=0;k--)
	{
		if(pars[a][k]!=pars[b][k])
		{
			a=pars[a][k];
			b=pars[b][k];
		}
	}
	
	return pars[a][0];
}

void dfs1(int u,int p)
{
	for(int v:adj[u])
	{
		if(v==p)
			continue;
		dfs1(v,u);
		up[u]+=up[v];
		dn[u]+=dn[v];
		
		if(up[v]>0 and dn[v]>0)
			bad=1;
	}
}

int main()
{
	cin>>q;
	while(q--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			adj[i].clear();
			up[i]=dn[i]=0;
		}
		for(int i=1;i<n;i++)
		{
			int a,b;
			cin>>a>>b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		dfs0(1,-1);
		for(int k=1;k<18;k++)
		{
			for(int v=1;v<=n;v++)
			{
				int p=pars[v][k-1];
				pars[v][k]=(p<0?-1:pars[p][k-1]);
			}
		}
		
		cin>>m;
		vector<pair<int,int>> prs(m);
		for(int i=0;i<m;i++)
		{
			int s,t;
			cin>>s>>t;
			prs[i]={s,t};
			int l=LCA(s,t);
			up[s]++;
			up[l]--;
			dn[t]++;
			dn[l]--;
		}
		
		bad=0;
		dfs1(1,-1);
		
		cout<<(bad?"No\n":"Yes\n");
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23