QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168282#857. Social DistancingkkioWA 566ms10524kbC++174.8kb2023-09-08 07:22:382023-09-08 07:22:38

Judging History

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

  • [2023-09-08 07:22:38]
  • 评测
  • 测评结果:WA
  • 用时:566ms
  • 内存:10524kb
  • [2023-09-08 07:22:38]
  • 提交

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.