ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213631 | #2769. 覆盖 | ThySecret | 30 | 4211ms | 1228kb | C++11 | 3.3kb | 2024-11-12 22:08:35 | 2024-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...