QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#38914 | #857. Social Distancing | _slb | AC ✓ | 1425ms | 16692kb | C++20 | 5.3kb | 2022-07-08 10:00:12 | 2022-07-08 10:00:14 |
Judging History
answer
// jiangly's method
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>
#include <cassert>
using namespace std;
namespace solve
{
const int maxn = 2010;
typedef pair<int, int> pii;
struct work
{
vector<vector<int>> e;
vector<pii> ans;
int now[maxn], dep[maxn], used[maxn], father[maxn];
void move(int x, int y)
{
assert(now[x]);
assert(!now[y]);
ans.push_back({x, y}), now[x] = 0, now[y] = 1;
}
void dfs1(int x, int fa)
{
father[x] = fa;
for (int v : e[x])
if (v != fa)
dep[v] = dep[x] + 1, dfs1(v, x);
}
int can_move(int x, int fa)
{
if (now[x])
return 0;
int res = 0;
for (int v : e[x])
if (v != fa)
res |= now[v];
return res == 0;
}
void try_move(int x, int fa)
{
for (int v : e[x])
if (v != fa && !used[v])
{
try_move(v, x);
if (can_move(v, x))
{
if (now[x])
{
move(x, v);
return;
}
}
}
}
int dfs2(int x, int fa)
{
vector<int> is;
for (int v : e[x])
if (v != fa && !used[v] && now[v])
is.push_back(v);
// cerr << x << " " << fa << " " << is.size() << endl;
if (is.size() == 0)
{
for (int v : e[x])
if (v != fa && !used[v])
{
int flag = dfs2(v, x);
if (flag)
{
assert(now[v]);
move(v, x);
return 1;
}
}
}
else if (is.size() == 1)
{
int v = is.front();
assert(now[v]);
move(v, x);
return 1;
}
else
{
int son = -1;
for (int v : is)
{
if (v == is.back() && son == -1)
{
son = v;
break;
}
try_move(v, x);
if (now[v])
{
if (son == -1)
son = v;
else
return 0;
}
}
move(son, x);
return 1;
}
return 0;
}
vector<pii> solve(int n, const vector<vector<int>> &edge_, const vector<int> &now_)
{
// cerr << "begin" << endl;
e = edge_;
for (int i = 1; i <= n; i++)
now[i] = now_[i];
ans.clear();
dfs1(1, 0);
vector<pii> tmp;
for (int i = 1; i <= n; i++)
tmp.push_back({dep[i], i});
sort(tmp.begin(), tmp.end(), greater<pii>());
for (auto o : tmp)
{
int x = o.second;
// cerr << x << endl;
if (!used[x] && !now[x])
dfs2(x, -1);
if (now[x])
for (int v : e[x])
used[v] = 1;
// for (int i = 1; i <= n; i++)
// cerr << now[i] << " ";
// cerr << endl;
}
for (int i = 1; i <= n; i++)
dep[i] = used[i] = father[i] = 0;
// cerr << "end" << endl;
return ans;
}
} S, T;
int check(int n)
{
for (int i = 1; i <= n; i++)
if (S.now[i] != T.now[i])
return 0;
return 1;
}
void main()
{
int n;
cin >> n;
vector<vector<int>> e(n + 1);
for (int i = 1, x, y; i < n; i++)
cin >> x >> y, e[x].push_back(y), e[y].push_back(x);
int k;
cin >> k;
vector<int> a(n + 1), b(n + 1);
for (int i = 1, x; i <= k; i++)
cin >> x, a[x] = 1;
for (int i = 1, x; i <= k; i++)
cin >> x, b[x] = 1;
auto res1 = S.solve(n, e, a), res2 = T.solve(n, e, b);
if (!check(n))
{
cout << "NO\n";
return;
}
cout << "YES" << '\n';
cout << res1.size() + res2.size() << '\n';
reverse(res2.begin(), res2.end());
for (auto p : res1)
cout << p.first << " " << p.second << '\n';
for (auto p : res2)
cout << p.second << " " << p.first << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
solve::main();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3556kb
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: 1425ms
memory: 3592kb
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 YES 18 10 17 4 13 13 15 14 18 1 5 2 6 6 4 4 6 6 2 18 14 14 3 15 13 17 10 10 12 13 15 7 11 5 1 8 16 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 ...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 731ms
memory: 3804kb
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 193 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 59 59...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 1166ms
memory: 4036kb
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 1689 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 1998 1998 1339 1339 881 881 1263 1263 1660 14 1441 1441 587 587 612 612...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 1207ms
memory: 16692kb
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: 571ms
memory: 8724kb
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 811 1717 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 1...
result:
ok OK!