ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213550 | #2769. 覆盖 | KXG | 60 | 42927ms | 362828kb | C++11 | 2.2kb | 2024-11-12 20:36:26 | 2024-11-12 23:34:34 |
answer
#include <cstdio>
#include <vector>
using namespace std;
struct BIT {
int n, t[2000010];
void modify(int k, int x) {
for (int i = k; i <= n; i += i & (-i)) {
t[i] += x;
}
}
int query(int k) {
int ans = 0;
for (int i = k; i >= 1; i -= i & (-i)) {
ans += t[i];
}
return ans;
}
} bt;
vector<int> ans;
int n, m, x, y, u, v;
vector<int> G[2000010];
vector<pair<int, int> > queries[2000010];
int fa[22][2000010], d[2000010], dfn[2000010], dfe[2000010], times;
void dfs(int u, int f = 0) {
dfn[u] = ++times;
fa[0][u] = f;
d[u] = d[f] + 1;
for (int v : G[u]) {
if (v == f) continue;
dfs(v, u);
}
dfe[u] = times;
}
void init() {
for (int i = 1; i < 22; i++) {
for (int j = 1; j <= n; j++) {
fa[i][j] = fa[i - 1][fa[i - 1][j]];
}
}
}
int lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = 21; i >= 0; i--) {
if (d[fa[i][y]] >= d[x]) {
y = fa[i][y];
}
}
if (x == y) return x;
for (int i = 21; i >= 0; i--) {
if (fa[i][x] != fa[i][y]) {
x = fa[i][x];
y = fa[i][y];
}
}
return fa[0][x];
}
void dfsxy(int u) {
for (int v : G[u]) {
if (v == fa[0][u]) continue;
dfsxy(v);
}
for (int i = 0; i < queries[u].size(); i++) {
int now = bt.query(dfn[queries[u][i].first]) + bt.query(dfn[queries[u][i].second]);
if (now == 0) {
ans.push_back(u);
bt.modify(dfn[u], 1);
bt.modify(dfe[u] + 1, -1);
break;
}
}
}
int main() {
scanf("%d", &n);
bt.n = n;
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
init();
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
queries[lca(x, y)].push_back({x, y});
}
dfsxy(1);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%d ", ans[i]);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 27ms
memory: 94944kb
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 10 3
result:
ok ok
Test #2:
score: 0
Accepted
time: 15ms
memory: 94940kb
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 13 6
result:
ok ok
Test #3:
score: 0
Accepted
time: 8ms
memory: 94948kb
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 11 4 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 19ms
memory: 94940kb
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 11 5
result:
ok ok
Test #5:
score: 0
Accepted
time: 24ms
memory: 94948kb
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 17 10 7 19 3 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 16ms
memory: 94948kb
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 13 4 9
result:
ok ok
Test #7:
score: 0
Accepted
time: 20ms
memory: 94944kb
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 8 5
result:
ok ok
Test #8:
score: 0
Accepted
time: 7ms
memory: 94944kb
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 10 4
result:
ok ok
Test #9:
score: 0
Accepted
time: 20ms
memory: 94944kb
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 10 8 3
result:
ok ok
Test #10:
score: 0
Accepted
time: 8ms
memory: 94944kb
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 12 7
result:
ok ok
Subtask #2:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 16ms
memory: 95080kb
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:
11 131 289 280 235 471 186 53 397 258 585 317
result:
ok ok
Test #12:
score: 0
Accepted
time: 11ms
memory: 95076kb
input:
1000 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 12 16 14 17 16 18 17 19 18 20 1...
output:
16 469 285 463 152 109 610 110 526 315 96 418 822 154 114 561 179
result:
ok ok
Test #13:
score: 0
Accepted
time: 16ms
memory: 95068kb
input:
1000 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 1...
output:
2 305 40
result:
ok ok
Test #14:
score: 0
Accepted
time: 37ms
memory: 97124kb
input:
1000 2 1 3 2 4 3 5 4 6 4 7 5 8 6 9 7 10 8 11 9 12 11 13 10 14 12 15 14 16 13 17 15 18 16 19 17 20 18...
output:
15 577 408 236 161 281 36 164 460 277 111 410 738 391 218 77
result:
ok ok
Test #15:
score: 0
Accepted
time: 12ms
memory: 95096kb
input:
1000 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 1...
output:
17 646 504 324 469 462 694 546 439 313 230 513 526 460 293 126 104 46
result:
ok ok
Test #16:
score: 0
Accepted
time: 17ms
memory: 95068kb
input:
1000 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 1...
output:
6 651 201 114 311 168 18
result:
ok ok
Test #17:
score: 0
Accepted
time: 7ms
memory: 95080kb
input:
1000 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 13 16 14 17 16 18 17 19 15 20 1...
output:
16 497 361 450 423 311 649 373 113 68 171 586 42 249 567 341 11
result:
ok ok
Test #18:
score: 0
Accepted
time: 17ms
memory: 95072kb
input:
1000 2 1 3 2 4 3 5 4 6 5 7 6 8 6 9 8 10 9 11 7 12 11 13 10 14 12 15 13 16 15 17 14 18 15 19 18 20 16...
output:
4 167 387 437 15
result:
ok ok
Test #19:
score: 0
Accepted
time: 12ms
memory: 95080kb
input:
1000 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 1...
output:
10 873 158 363 364 978 372 236 367 33 210
result:
ok ok
Test #20:
score: 0
Accepted
time: 4ms
memory: 95068kb
input:
1000 2 1 3 2 4 3 5 4 6 5 7 6 8 3 9 8 10 9 11 10 12 11 13 7 14 12 15 13 16 7 17 14 18 17 19 15 20 16 ...
output:
5 307 7 241 118 85
result:
ok ok
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 40
Accepted
time: 1668ms
memory: 353368kb
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:
5 49620 10715 260 23494 16698
result:
ok ok
Test #22:
score: 0
Accepted
time: 1639ms
memory: 354212kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
45 11229 7524 58888 181476 187293 688613 250167 98852 37754 242712 222879 91612 486244 286931 164683...
result:
ok ok
Test #23:
score: 0
Accepted
time: 1893ms
memory: 358256kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
288 337025 168778 522156 341203 577622 308988 97622 194033 1341353 370758 787195 433073 834931 49484...
result:
ok ok
Test #24:
score: 0
Accepted
time: 1737ms
memory: 356804kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
172 1014013 529921 694297 520180 599257 631816 181786 129828 470110 445132 69263 79221 260919 141973...
result:
ok ok
Test #25:
score: 0
Accepted
time: 3347ms
memory: 362828kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
635 632643 1062517 615615 1321467 974900 624121 1147835 604799 554132 676563 943663 420074 254648 44...
result:
ok ok
Test #26:
score: 0
Accepted
time: 1566ms
memory: 353952kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
27 71286 172800 135166 27608 485335 7509 555946 56909 166820 34761 302153 119648 199173 81891 104143...
result:
ok ok
Test #27:
score: 0
Accepted
time: 1547ms
memory: 353300kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
6 83430 5695 8562 34548 3177 490
result:
ok ok
Test #28:
score: 0
Accepted
time: 2011ms
memory: 357240kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
220 305408 533550 282162 1340502 836376 1936525 761348 332688 909621 948215 251198 326676 68125 8624...
result:
ok ok
Test #29:
score: 0
Accepted
time: 1558ms
memory: 353632kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
18 52501 14974 76116 77795 39104 68915 217782 16009 181356 77646 40324 373647 28264 2171 45067 56381...
result:
ok ok
Test #30:
score: 0
Accepted
time: 1651ms
memory: 354420kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
45 581336 45646 525980 126715 611688 71846 40197 108135 217236 12786 61559 22736 135687 26716 172073...
result:
ok ok
Test #31:
score: 0
Accepted
time: 1534ms
memory: 354120kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
32 157325 1248806 49460 54106 27779 395244 156949 60225 79924 406005 112588 23813 63492 49619 60014 ...
result:
ok ok
Test #32:
score: 0
Accepted
time: 1724ms
memory: 353388kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
5 80900 19941 5384 6708 15117
result:
ok ok
Test #33:
score: 0
Accepted
time: 1542ms
memory: 353596kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
11 35897 299866 16347 44930 8344 6325 326571 57419 46860 78545 4421
result:
ok ok
Test #34:
score: 0
Accepted
time: 1527ms
memory: 353216kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
2 7452 5187
result:
ok ok
Test #35:
score: 0
Accepted
time: 1819ms
memory: 356916kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
192 798022 683274 189151 272780 395686 178707 167947 288168 84233 42016 213201 246297 65882 401226 3...
result:
ok ok
Test #36:
score: 0
Accepted
time: 2452ms
memory: 360848kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
489 1290894 773197 168673 549010 1110040 463781 101013 564050 878684 504977 144833 550142 490628 583...
result:
ok ok
Test #37:
score: 0
Accepted
time: 1564ms
memory: 353288kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
2 10047 1572
result:
ok ok
Test #38:
score: 0
Accepted
time: 1630ms
memory: 353508kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
6 124227 21899 342086 17244 16799 5177
result:
ok ok
Test #39:
score: 0
Accepted
time: 1554ms
memory: 353388kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
3 37101 114239 9574
result:
ok ok
Test #40:
score: 0
Accepted
time: 2307ms
memory: 359896kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
434 231435 1065369 1047494 1043183 862445 364587 150861 935117 12689 107063 890252 1119825 316606 21...
result:
ok ok
Test #41:
score: 0
Accepted
time: 1556ms
memory: 353320kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
3 18588 12701 4025
result:
ok ok
Test #42:
score: 0
Accepted
time: 1571ms
memory: 354288kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
46 345372 63057 30104 12634 247470 129242 189949 23016 135187 397173 307574 181178 172800 241086 788...
result:
ok ok
Test #43:
score: 0
Accepted
time: 1628ms
memory: 353616kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
9 48149 7458 71934 30431 45809 29074 16676 19276 12356
result:
ok ok
Test #44:
score: 0
Accepted
time: 1589ms
memory: 353772kb
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 13 15 14 16 15 17 16 18 17 19 18 2...
output:
21 59568 320093 304055 58508 71429 596841 34965 8870 337494 154795 42583 147513 149176 207708 7530 5...
result:
ok ok
Test #45:
score: -40
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 13 15 14 16 15 17 16 18 17 19 18 2...