QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168282 | #857. Social Distancing | kkio | WA | 566ms | 10524kb | C++17 | 4.8kb | 2023-09-08 07:22:38 | 2023-09-08 07:22:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
struct IO {
char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
IO() : iS(ibuf), iT(ibuf), oS(obuf) {} ~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == 't' || ch == EOF; }
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void read (char *s) {
char ch = gh(); int l = 0;
while (eof(ch)) ch = gh();
while (!eof(ch)) s[l++] = ch, ch = gh();
}
inline void read (double &x) {
char ch = gh(); bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
if (ch != '.') return t && (x = -x), void(); ch = gh();
for (double cf = 0.1; '0' <= ch && ch <= '9'; ch = gh(), cf *= 0.1) x += cf * (ch ^ 48);
t && (x = -x);
}
inline void pc (char ch) {
#ifdef ONLINE_JUDGE
if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
*oS++ = ch;
#else
putchar(ch);
#endif
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
inline void write (char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) pc(s[i]);
}
} io;
inline long long read () { return io.read(); }
template<typename Tp>
inline void read (Tp &x) { io.read(x); }
template<typename _Tp>
inline void write (_Tp x) { io.write(x); }
}
using namespace FastIO;
const int maxn=1e5+10;
int n,k,a[maxn],b[maxn],tz1[maxn],tz2[maxn],dep[maxn],p[maxn],ct[maxn];
vector<int> G[maxn];
vector< pair<int,int> > SA,SB;
void predfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for(int v:G[u])
if(v!=fa)
predfs(v,u);
}
bool spindfs(int u,int fa,int *d,int *c,vector< pair<int,int> > &A)
{
int flag=0,cm=0,cnt=0;
for(int v:G[u])
if(v!=fa)
{
if(d[v]&&c[v])flag=1;
else if(d[v]&&!c[v])cm=v,cnt++;
}
if(flag)return 0;
if(cnt==1)
{
A.emplace_back(cm,u);
//rintf("@%d %d\n",cm,u);
swap(d[u],d[cm]);
return 1;
}
if(!cnt)
{
for(int v:G[u])
if(v!=fa&&spindfs(v,u,d,c,A))
{
// printf("#%d %d\n",v,u);
A.emplace_back(v,u);
swap(d[v],d[u]);
return 1;
}
}
return 0;
}//将任意节点旋到深度最大的点
int levdfs(int u,int fa,int *d,int *c,vector< pair<int,int> > &A)
{
if(c[u])return 0;
if(d[u])
{
for(int v:G[u])
if(v!=fa&&levdfs(v,u,d,c,A)>=2)
{
// printf("?%d %d\n",u,v);
A.emplace_back(u,v);
swap(d[u],d[v]);
return 1;
}
return 0;
}
else
{
int mn=1e9;
for(int v:G[u])
if(v!=fa)
mn=min(mn,levdfs(v,u,d,c,A));
return mn;
}
}//将卡住路径的节点拉远
void solve()
{
n=read();
SA.clear();SB.clear();
for(int i=1;i<=n;i++)G[i].clear(),tz1[i]=tz2[i]=ct[i]=0;
for(int i=1,u,v;i<n;i++)
{
u=read(),v=read();
G[u].push_back(v);
G[v].push_back(u);
}
k=read();
for(int i=1;i<=k;i++)
a[i]=read(),tz1[a[i]]=1;
for(int i=1;i<=k;i++)
b[i]=read(),tz2[b[i]]=1;
predfs(1,0);for(int i=1;i<=n;i++)p[i]=i;sort(p+1,p+1+n,[&](int a,int b){return dep[a]>dep[b];});
for(int i=1;i<=n;i++)
{
int u=p[i];
if(!tz1[u])levdfs(u,0,tz1,ct,SA),spindfs(u,0,tz1,ct,SA);
if(!tz2[u])levdfs(u,0,tz2,ct,SB),spindfs(u,0,tz2,ct,SB);
ct[u]=1;
}
for(int i=1;i<=n;i++)if(tz1[i]!=tz2[i])
{
puts("NO");
return;
}
puts("YES");
printf("%d\n",SA.size()+SB.size());
for(auto [u,v]:SA)printf("%d %d\n",u,v);
reverse(SB.begin(),SB.end());
for(auto [u,v]:SB)printf("%d %d\n",v,u);
return;
}
int main()
{
int T;
scanf("%d\n",&T);
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10012kb
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: 566ms
memory: 10524kb
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 9 6 18 8 15 1 3 3 17 17 3 3 1 14 7 5 4 1 3 NO NO NO NO YES 8 1 11 4 9 11 1 1 2 9 4 4 6 12 15 8 14 YES 14 10 12 12 10 10 11 14 1 2 13 6 8 17 18 1 14 14 1 8 6 6 3 11 10 10 12 12 10 YES 18 10 17 15 1 12 5 5 9 11 16 16 7 3 6 6 8 1 15 1...
result:
wrong answer Contestant did not find a solution, but jury did.