ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213649 | #2769. 覆盖 | STASISZHY | 0 | 1833ms | 400216kb | C++11 | 2.3kb | 2024-11-12 22:39:23 | 2024-11-13 00:05:24 |
answer
// Problem: C. 覆盖
// Contest: undefined - NOIP2024训练赛 03
// URL: http://119.28.3.174/contest/1155/problem/2769
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 2e6 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, q, ans, ti;
int dp[N], dep[N], f[N][35], sum[N], dfn[N];
// map<PII, int> id;
struct node
{
int lca, x, y;
}s[N];
inline bool cmp(node a, node b) {return dep[a.lca] > dep[b.lca];}
vector<int> e[N], v;
void dfs(int now, int fa)
{
dep[now] = dep[fa] + 1, f[now][0] = fa, dfn[now] = ++ ti;
for(auto i : e[now]) if(i != fa) dfs(i, now);
}
inline int lca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int i = 30; ~ i; i --) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
// cout << "x = " << x << " y = " << y << '\n';
if(x == y) return x;
for(int i = 30; ~ i; i --) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
inline bool check(int i, int now)
{
// cout << "lst = " << i << " lca = " << s[now].lca << '\n';
if(lca(i, s[now].lca) == s[now].lca && lca(i, s[now].x) == i) return true;
if(lca(i, s[now].lca) == s[now].lca && lca(i, s[now].y) == i) return true;
return false;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i < n; i ++)
{
int u, v; cin >> u >> v;
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 0);
// for(int i = 1; i <= n; i ++) cout << dfn[i] << ' ';
// cout << '\n';
for(int j = 1; j <= 30; j ++)
for(int i = 1; i <= n; i ++) f[i][j] = f[f[i][j - 1]][j - 1];
cin >> q;
for(int i = 1; i <= q; i ++)
{
int x, y; cin >> x >> y;
s[i] = {lca(x, y), x, y};
}
sort(s + 1, s + q + 1, cmp);
// cout << s[1].lca << '\n';
// cout << lca(10, 8) << '\n';
int lst = s[1].lca; v.push_back(s[1].lca);
for(int i = 2; i <= q; i ++)
{
if(check(lst, i)) continue;
// cout << s[i].x << ' ' << s[i].y << '\n';
v.push_back(s[i].lca), lst = s[i].lca;
}
cout << v.size() << '\n';
sort(v.begin(), v.end());
for(auto i : v) cout << i << ' ';
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 11ms
memory: 48164kb
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: 4ms
memory: 48160kb
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: 4ms
memory: 48168kb
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: 3ms
memory: 48160kb
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: 7ms
memory: 48164kb
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: -30
Wrong Answer
time: 4ms
memory: 48164kb
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:
4 2 4 9 13
result:
wrong answer Arrangement not optimal
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 4ms
memory: 48336kb
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:
24 3 5 23 53 78 80 98 101 110 131 182 186 206 235 250 261 275 280 289 317 397 407 471 585
result:
wrong answer Arrangement not optimal
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 1796ms
memory: 400216kb
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:
6 260 10715 16698 19031 23494 49620
result:
wrong answer Arrangement not optimal