ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213522 | #2769. 覆盖 | nodgd | 0 | 0ms | 1324kb | C++11 | 2.2kb | 2024-11-12 19:45:37 | 2024-11-12 23:19:43 |
answer
#include <bits/stdc++.h>
using namespace std;
namespace FastRead{
char buf[1000005], *s = buf, *t = buf, ch, f;
#define gc() s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++
template <typename T>
inline void Read(T &x)
{
x = f = 0, ch = gc();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = 1;
ch = gc();
}
while('0' <= ch && ch <= '9') x = x * 10 + ch - 48, ch = gc();
f && (x = -x);
}
};
using FastRead::Read;
const int N = 2e6 + 5, K = 22;
int n, m;
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N][K], dep[N], in[N], out[N], dfst;
struct Node{
int u, v, w, d;
bool operator <(const Node &w) const
{
return d > w.d;
}
}x[N];
int cnt, vis[N], c[N];
inline void Add(int a, int b)
{
ne[ ++ idx] = la[a];
la[a] = idx;
en[idx] = b;
}
inline void DFS(int u, int f)
{
fa[u][0] = f, dep[u] = dep[f] + 1;
for(int i = 1; i < K; i ++ ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
in[u] = ++ dfst;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(v != f) DFS(v, u);
}
out[u] = dfst;
}
inline int LCA(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(int i = K - 1; i >= 0; i -- )
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = K - 1; i >= 0; i -- )
if(fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
inline void Modify(int i, int d)
{
for(; i <= n; i += i & -i) c[i] += d;
}
inline int Sum(int i)
{
int s = 0;
for(; i; i &= i - 1) s += c[i];
return s;
}
int main()
{
Read(n), Read(m);
for(int i = 1; i < n; i ++ )
{
int a, b;
Read(a), Read(b);
Add(a, b), Add(b, a);
}
DFS(1, 0);
for(int i = 1; i <= m; i ++ )
{
Read(x[i].u), Read(x[i].v);
x[i].w = LCA(x[i].u, x[i].v);
x[i].d = dep[x[i].w];
}
sort(x + 1, x + m + 1);
for(int i = 1; i <= m; i ++ )
{
// printf("*%d %d %d\n", x[i].u, x[i].v, x[i].w);
if(Sum(in[x[i].u]) + Sum(in[x[i].v]) - Sum(in[x[i].w]) - Sum(in[fa[x[i].w][0]]) == 0)
{
vis[x[i].w] = 1;
cnt ++ ;
Modify(in[x[i].w], 1);
Modify(out[x[i].w] + 1, -1);
}
}
printf("%d\n", cnt);
for(int i = 1; i <= n; i ++ ) if(vis[i]) printf("%d ", i);
puts("");
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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:
result:
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 1324kb
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:
1 80
result:
wrong answer Arrangement not valid
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
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...