QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#39138 | #857. Social Distancing | wind_whisper | AC ✓ | 855ms | 11600kb | C++14 | 3.5kb | 2022-07-08 15:14:14 | 2022-07-08 15:14:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ULL unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read() {
ll x(0),f(1);char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=2050;
const int mod=100000000;
const ll inf=1e9;
bool mem1;
bool Flag=0;
int n,m;
vector<int>e[N];
int dep[N];
void init(int x,int f){
dep[x]=dep[f]+1;
for(int to:e[x]){
if(to==f) continue;
init(to,x);
}
return;
}
int a[N],b[N];
int col[N];
int u[N*N],v[N*N],tot;
inline void move(int x,int y){
assert(col[x]&&!col[y]);
col[x]^=1;
col[y]^=1;
++tot;
u[tot]=x;v[tot]=y;
}
inline void rollback(int goal){
while(tot!=goal){
col[u[tot]]^=1;
col[v[tot]]^=1;
--tot;
}
return;
}
int nod[N];
bool cmp(int x,int y){
return dep[x]>dep[y];
}
bool exi[N],tag[N];
bool clear(int x,int fa);
bool leave(int x,int fa){//make a black x leave
if(tag[x]) return false;
for(int to:e[x]){
if(to==fa||tag[to]) continue;
if(clear(to,x)){
move(x,to);
return true;
}
}
return false;
}
bool clear(int x,int fa){//make white x's neighbour white
if(tag[x]) return false;
int tim=tot;
for(int to:e[x]){
if(to==fa) continue;
if(tag[to]&&col[to]){
rollback(tim);
return false;
}
if(!col[to]) continue;
if(leave(to,x)) continue;
rollback(tim);
return false;
}
return true;
}
bool dfs(int x,int fa){
if(tag[x]) return false;
if(col[x]) return true;
int tim=tot;
int cnt(0);
for(int to:e[x]){
if(to==fa) continue;
if(tag[to]&&col[to]) return false;
cnt+=col[to];
}
//printf(" dfs: x=%d fa=%d col=%d cnt=%d\n",x,fa,col[x],cnt);
if(!cnt){
for(int to:e[x]){
if(to==fa||tag[to]) continue;
if(dfs(to,x)){
move(to,x);
return true;
}
}
return false;
}
else{
int now=0;
for(int to:e[x]){
if(to==fa||tag[to]) continue;
if(!col[to]) continue;
--cnt;
if(cnt==0&&!now) now=to;
else if(!leave(to,x)){
if(!now) now=to;
else{
rollback(tim);
return false;
}
}
}
move(now,x);
return true;
}
rollback(tim);
return false;
}
void work(){
n=read();tot=0;
for(int i=1;i<=n;i++){
e[i].clear();
}
for(int i=1;i<n;i++){
int x=read(),y=read();
e[x].push_back(y);
e[y].push_back(x);
}
m=read();
for(int i=1;i<=m;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
init(1,0);
for(int i=1;i<=n;i++){
col[i]=0;
tag[i]=0;
nod[i]=i;
exi[i]=0;
}
for(int i=1;i<=m;i++) col[a[i]]=1;
sort(nod+1,nod+1+n,cmp);
for(int i=1;i<=n;i++){
int x=nod[i];
exi[x]=dfs(x,0);
//printf("x=%d exi=%d\n",x,exi[x]);
tag[x]=1;
}
int pos=tot;
//printf("--- pos=%d\n",pos);
for(int i=1;i<=n;i++){
col[i]=0;
tag[i]=0;
}
for(int i=1;i<=m;i++) col[b[i]]=1;
for(int i=1;i<=n;i++){
int x=nod[i];
if(!exi[x]){
continue;
tag[x]=1;
}
//printf("x=%d\n",x);
if(!dfs(x,0)){
puts("NO");
return;
}
tag[x]=1;
}
for(int i=pos+1;i<=tot;i++) swap(u[i],v[i]);
reverse(u+pos+1,u+tot+1);
reverse(v+pos+1,v+tot+1);
puts("YES");
printf("%d\n",tot);
for(int i=1;i<=tot;i++) printf("%d %d\n",u[i],v[i]);
return;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
while(T--) work();
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
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: 0
Accepted
time: 298ms
memory: 5660kb
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 1 19 2 NO NO NO NO NO YES 7 8 15 6 18 1 3 3 17 17 3 14 7 5 4 YES 18 10 17 4 13 13 15 14 18 1 5 2 6 6 4 4 6 6 2 5 1 8 16 18 14 14 3 15 13 7 11 17 10 10 12 13 15 NO NO NO YES 8 4 9 1 11 11 1 1 2 12 15 8 14 9 4 4 6 YES 8 10 11 17 18 6 8 2 13 14 1 8 6 6 3 11 10 YES 18 12 5...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 250ms
memory: 5784kb
input:
1703 165 137 77 32 123 34 74 18 16 79 88 130 10 74 151 112 48 78 91 135 132 145 19 51 19 103 37 13 57 36 157 84 87 48 158 72 161 149 50 89 49 37 8 71 47 85 32 126 35 46 111 119 135 30 53 130 158 123 70 97 109 25 21 16 55 158 118 46 24 77 130 101 23 50 88 13 96 88 22 162 128 125 86 165 106 163 63 75 ...
output:
YES 199 61 96 96 133 133 118 118 158 158 48 48 74 74 151 151 155 155 110 110 65 160 103 103 133 133 118 118 158 158 48 48 74 74 35 35 156 156 62 119 135 135 8 8 37 37 103 103 133 133 118 118 158 158 48 48 74 74 151 151 155 155 29 30 53 53 135 135 8 8 37 37 103 103 133 133 118 118 158 158 48 48 74 74...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 227ms
memory: 5900kb
input:
10 2000 1768 1996 1796 195 468 1622 1574 1483 489 1043 257 1318 1288 818 1654 1667 695 1592 974 17 274 1323 116 1169 1052 1404 1568 1163 960 1695 802 950 544 419 595 238 1901 585 888 1527 1861 402 1186 353 1479 1805 373 955 1513 1254 1084 1403 1425 1630 1371 1881 574 1254 1749 806 1784 615 1705 511 ...
output:
NO NO NO NO NO NO NO YES 1655 1915 1119 1119 485 485 813 813 1139 1139 259 259 1842 1842 569 569 1998 1998 602 602 147 147 516 516 1359 1359 1303 1975 471 471 130 130 1580 1580 485 485 813 813 1139 1139 259 259 1842 1842 569 569 244 244 1282 1282 321 321 1013 1013 369 1824 740 740 1483 1483 485 485 ...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 855ms
memory: 11600kb
input:
10 1989 1562 1958 831 864 1079 73 509 988 920 770 498 1214 877 1208 211 1899 905 98 834 197 1054 1147 748 1041 923 816 1138 1592 129 1250 1091 1455 639 1720 1975 208 625 1692 884 1431 1128 1367 688 2 741 444 1462 1734 68 1133 1309 1666 1769 734 844 1372 275 134 1941 399 1110 1010 715 220 1133 1111 3...
output:
YES 495012 1657 882 882 635 635 1366 1366 1184 1184 1496 1496 309 309 1005 1005 201 201 858 858 110 110 541 541 221 221 770 770 920 920 1922 1922 437 437 269 269 223 223 236 236 1201 1201 1566 1566 1913 1913 1818 1818 222 222 583 583 1919 1919 181 181 1536 1536 1564 1564 1794 1794 948 948 691 691 25...
result:
ok OK!
Test #6:
score: 0
Accepted
time: 232ms
memory: 9264kb
input:
11 1981 1974 1563 23 1887 1820 1714 1134 840 1134 275 571 76 1536 1739 875 821 1857 1114 1110 860 787 1671 1676 1478 1335 480 1885 432 119 438 363 1743 447 96 667 651 1571 816 590 1452 557 1339 185 1119 1643 459 1638 1614 807 266 730 737 404 686 465 1796 202 214 1210 227 1402 1238 744 494 1435 1804 ...
output:
YES 130186 693 780 330 919 1906 537 869 1629 1185 488 803 1971 1171 823 352 1605 1764 1902 320 319 162 1419 1759 1960 90 1698 1616 1871 184 690 466 1351 64 17 1862 1039 653 193 1418 764 636 1530 960 458 489 1191 814 1084 1555 585 27 1318 966 666 502 1099 790 1549 1926 1733 356 1859 1188 36 873 47 19...
result:
ok OK!