QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430718#857. Social DistancingNaganohara_YoimiyaWA 322ms3828kbC++142.9kb2024-06-04 11:13:112024-06-04 11:13:12

Judging History

你现在查看的是最新测评结果

  • [2024-06-04 11:13:12]
  • 评测
  • 测评结果:WA
  • 用时:322ms
  • 内存:3828kb
  • [2024-06-04 11:13:11]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=2005;
vector<int>G[N];
bool vis[N],In[N];
int n,dep[N];

vector<pair<int,int> >ans;
void mov(int x,int y){In[x]=0,In[y]=1,ans.emplace_back(mk(x,y));}

void dfs(int u,int fa){
	for(int v:G[u])if(v!=fa)dep[v]=dep[u]+1,dfs(v,u);
}
bool Down(int u,int fa){
	bool ret=true;
	for(int v:G[u])if(v!=fa&&(!vis[v])){
		if(Down(v,u))mov(u,v);
		ret&=(!In[v]);
	}
	ret&=(!In[u]);
	return ret;
}
bool Up(int u,int fa){
	vector<int>sons;
	for(int v:G[u])if(v!=fa&&(!vis[v])){
		if(In[v])sons.emplace_back(v);
	}
	if(sons.size()==0){
		for(int v:G[u])if(v!=fa&&(!vis[v])){
			if(Up(v,u))return mov(v,u),true;
		}
		return false;
	}
	else if(sons.size()==1){
		return mov(sons[0],u),true;
	}
	else{
		int p=0;
		for(int v:sons){
			Down(v,u);
			if(In[v]){
				if(p)return false;
				p=v;
			}
		}
		if(!p)p=sons[0];
		return mov(p,u),true;
	}
}

pair<vector<pair<int,int> >,vector<int> >Solve(vector<int>S){
	for(int i=1;i<=n;i++)vis[i]=In[i]=0;
	for(int i:S)In[i]=true;ans.clear();
	// cout<<"Solve S = ";for(int i:S)cout<<i<<" ";puts("");

	vector<pair<int,int> >nodes(n);
	for(int i=1;i<=n;i++)nodes[i-1]=mk(dep[i],i);
	sort(nodes.begin(),nodes.end()),reverse(nodes.begin(),nodes.end());

	for(auto [d,u]:nodes){
		// cout<<"try u = "<<u<<endl;
		if(vis[u])continue;
		if(!In[u])Up(u,0);
		if(In[u])for(int v:G[u])vis[v]=true;
	}

	vector<int>S0;
	for(int i=1;i<=n;i++)if(In[i])S0.emplace_back(i);
	return mk(ans,S0);
}

void solve(){
	n=read();
	for(int i=2;i<=n;i++){
		int u=read(),v=read();
		G[u].emplace_back(v),G[v].emplace_back(u);
	}
	int k=read();vector<int>S(k),T(k);
	for(int i=0;i<k;i++)S[i]=read();
	for(int i=0;i<k;i++)T[i]=read();

	dep[1]=0,dfs(1,0);

	auto [aS,pS]=Solve(S);auto [aT,pT]=Solve(T);
	if(pS!=pT)puts("NO");
	else{
		puts("YES");
		cout<<aS.size()+aT.size()<<'\n';
		for(auto [x,y]:aS)cout<<x<<" "<<y<<'\n';
		reverse(aT.begin(),aT.end());
		for(auto [x,y]:aT)cout<<y<<" "<<x<<'\n';
	}

	for(int i=1;i<=n;i++)G[i].clear();
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif

	int tt=read();while(tt--)solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

input:

2
5
1 2
1 3
2 4
2 5
2
1 4
1 5
7
1 2
2 3
2 4
4 6
6 5
6 7
3
1 4 5
3 4 7

output:

YES
4
1 3
4 2
2 5
3 1
NO

result:

ok OK!

Test #2:

score: -100
Wrong Answer
time: 322ms
memory: 3696kb

input:

100000
18
16 7
18 3
13 8
12 16
17 10
12 4
9 15
2 5
13 6
17 11
12 1
5 6
3 2
17 2
1 2
4 15
14 17
7
1 6 8 15 16 17 18
2 10 11 12 13 14 18
19
3 10
3 5
15 7
9 18
3 9
19 11
11 17
10 4
14 17
7 17
6 9
15 2
12 17
9 8
5 11
9 13
1 13
3 16
9
2 4 5 8 13 16 17 18 19
2 3 4 6 8 13 17 18 19
20
20 14
6 10
3 13
10 4
7...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
3
19 15
15 19
19 2
NO
NO
NO
NO
NO
YES
7
8 15
6 18
1 3
3 17
17 3
14 7
5 4
NO
NO
NO
NO
YES
8
4 9
1 11
11 1
1 2
8 14
12 15
9 4
4 6
YES
8
17 18
10 12
6 16
2 13
14 1
16 6
6 3
12 10
YES
10
10 17
15 1
3 6
6 8
1 15
15 1
8 6
17 10
18 13
12 5
NO
NO
YES
4
8 12
9 11
12 8
4 14
NO
N...

result:

wrong answer Contestant did not find a solution, but jury did.