QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430718 | #857. Social Distancing | Naganohara_Yoimiya | WA | 322ms | 3828kb | C++14 | 2.9kb | 2024-06-04 11:13:11 | 2024-06-04 11:13:12 |
Judging History
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.