제출 #565202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565202		MohamedAhmed04	Jail (JOI22_jail)	C++14	49 / 100	155 ms	6880 KiB

jail

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , m ;

vector< vector<int> >adj(MAX) ;

int a[MAX] , b[MAX] ;
int mark[MAX] , cnt[MAX] ;

int dep[MAX] , P[MAX] ;

void dfs(int node , int par)
{
	P[node] = par ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dep[child] = dep[node] + 1 ;
		dfs(child , node) ;
	}
}

void gopath(int x , int y , int val)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	while(x != y)
	{
		cnt[x] += val ;
		x = P[x] ;
		if(dep[x] < dep[y])
			swap(x , y) ;
	}
	cnt[x] += val ;
}

bool check(int x , int y)
{
	if(cnt[y] != 1)
		return false ;
	if(dep[x] < dep[y])
		swap(x , y) ;
	int cur = 0 ;
	while(x != y)
	{
		cur += mark[x] ;
		x = P[x] ;
		if(dep[x] < dep[y])
			swap(x , y) ;
	}
	cur += mark[x] ;
	return (cur == 1) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	int t ;
	cin>>t ;
	while(t--)
	{
		cin>>n ;
		for(int i = 1 ; i <= n ; ++i)
			adj[i].clear() , mark[i] = cnt[i] = 0 ;
		for(int i = 0 ; i < n-1 ; ++i)
		{
			int x , y ;
			cin>>x>>y ;
			adj[x].push_back(y) ;
			adj[y].push_back(x) ;
		}
		cin>>m ;
		for(int i = 1 ; i <= m ; ++i)
			cin>>a[i]>>b[i] ;
		dfs(1 , 0) ;
		for(int i = 1 ; i <= m ; ++i)
			mark[a[i]] = 1 , gopath(a[i] , b[i] , 1) ;
		int now = 0 ;
		for(int i = 1 ; i <= m ; ++i)
		{
			for(int j = 1 ; j <= m ; ++j)
			{
				if(!mark[a[j]])
					continue ;
				if(check(a[j] , b[j]))
					++now , gopath(a[j] , b[j] , -1) , mark[a[j]] = 0 ;
			}
		}
		if(now == m)
			cout<<"Yes\n" ;
		else
			cout<<"No\n" ;
	}
	return 0 ;
}		

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