UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213631#2769. 覆盖ThySecret304211ms1228kbC++113.3kb2024-11-12 22:08:352024-11-12 23:59:06

answer

#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 110;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m, minn = INF;
int h[N], e[N << 1], ne[N << 1], idx;
int depth[N], fa[N][10], tag[N];
array<int, 2> edge[N];
vector<int> ans;

inline void add(int a, int b) { e[++ idx] = b, ne[idx] = h[a], h[a] = idx; }

void dfs(int ver, int pre)
{
    depth[ver] = depth[pre] + 1, fa[ver][0] = pre;
    for (int k = 1; k < 10; k ++)
        fa[ver][k] = fa[fa[ver][k - 1]][k - 1];
    for (int i = h[ver]; ~i; i = ne[i])
    {
        int to = e[i];
        if (to == pre) continue;
        dfs(to, ver);
    }
}

int LCA(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 9; ~k; k --)
        if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    if (a == b) return a;
    for (int k = 9; ~k; k --)
        if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

signed main()
{
    memset(h, -1, sizeof h), idx = -1;
    read(n);
    for (int i = 1; i < n; i ++)
    {
        int a, b; read(a, b);
        add(a, b), add(b, a);
    }

    read(m);
    for (int i = 1; i <= m; i ++)
        read(edge[i][0], edge[i][1]);
    dfs(1, 0);

    for (int state = 0; state < 1 << n; state ++)
    {
        memset(tag, 0, sizeof tag);
        for (int ver = 0; ver < n; ver ++)
            if (state >> ver & 1) tag[ver + 1] = true;

        bool flag = true;
        for (int i = 1; i <= m; i ++)
        {
            int lca = LCA(edge[i][0], edge[i][1]);
            if (tag[lca]) continue;
            bool ok = false;
            for (int cur = edge[i][0]; cur != lca; cur = fa[cur][0])
                if (tag[cur])
                {
                    ok = true;
                    break;
                }
            if (ok) continue;
            for (int cur = edge[i][1]; cur != lca; cur = fa[cur][0])
                if (tag[cur])
                {
                    ok = true;
                    break;
                }
            if (!ok)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            if (minn > __builtin_popcount(state))
            {
                minn = __builtin_popcount(state);
                ans.clear();
                for (int ver = 1; ver <= n; ver ++)
                    if (tag[ver]) ans.push_back(ver); 
            }
        }
    }

    cout << minn << '\n';
    for (int ver : ans) cout << ver << ' ';
    cout << '\n';

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 302ms
memory: 1220kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 13
17 15
18 16
19 17
20 18
...

output:

2
3 10 

result:

ok ok

Test #2:

score: 0
Accepted
time: 536ms
memory: 1224kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
6 13 

result:

ok ok

Test #3:

score: 0
Accepted
time: 276ms
memory: 1228kb

input:

20
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 8
10 9
11 10
12 6
13 2
14 7
15 14
16 11
17 12
18 17
19 7
20 15
5
4 ...

output:

3
1 4 11 

result:

ok ok

Test #4:

score: 0
Accepted
time: 629ms
memory: 1220kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 508ms
memory: 1228kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 6
10 8
11 10
12 11
13 11
14 12
15 13
16 9
17 15
18 16
19 16
20 17
1...

output:

6
1 3 7 10 17 19 

result:

ok ok

Test #6:

score: 0
Accepted
time: 385ms
memory: 1228kb

input:

20
2 1
3 2
4 3
5 3
6 5
7 4
8 6
9 8
10 7
11 7
12 10
13 12
14 13
15 9
16 14
17 16
18 16
19 17
20 15
12...

output:

3
4 9 13 

result:

ok ok

Test #7:

score: 0
Accepted
time: 173ms
memory: 1224kb

input:

20
2 1
3 1
4 2
5 3
6 4
7 5
8 6
9 7
10 8
11 9
12 10
13 11
14 10
15 14
16 10
17 13
18 4
19 18
20 4
2
1...

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 301ms
memory: 1224kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 4
8 7
9 6
10 9
11 8
12 11
13 10
14 10
15 12
16 14
17 13
18 17
19 14
20 18
4...

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 529ms
memory: 1228kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 8
12 10
13 12
14 8
15 13
16 8
17 8
18 16
19 15
20 11
12
8...

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 572ms
memory: 1224kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 7
10 9
11 10
12 8
13 11
14 12
15 13
16 14
17 15
18 16
19 18
20 19
1...

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 11
15 14
16 13
17 15
18 16
19 17
2...

output:


result: