QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#38914#857. Social Distancing_slbAC ✓1425ms16692kbC++205.3kb2022-07-08 10:00:122022-07-08 10:00:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-08 10:00:14]
  • 评测
  • 测评结果:AC
  • 用时:1425ms
  • 内存:16692kb
  • [2022-07-08 10:00:12]
  • 提交

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();
}

详细

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!