QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378739 | #8575. Three Person Tree Game | ucup-team2112# | AC ✓ | 72ms | 35232kb | C++20 | 4.3kb | 2024-04-06 14:27:03 | 2024-04-06 14:27:03 |
Judging History
answer
#include <bits/stdc++.h>
struct HLD {
int n;
std::vector<int> sz, top, dep, parent, in, out, seq;
std::vector<std::vector<int>> adj;
int dfs_clock;
HLD() {}
HLD(int n) {
init(n);
}
void init(int n) {
this->n = n;
sz.resize(n);
top.resize(n);
dep.resize(n);
parent.resize(n);
in.resize(n);
out.resize(n);
seq.resize(n);
dfs_clock = 0;
adj.assign(n, {});
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void work(int root = 0) {
top[root] = root;
dep[root] = 0;
parent[root] = -1;
dfs1(root);
dfs2(root);
}
void dfs1(int u) {
if (parent[u] != -1) {
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
}
sz[u] = 1;
for (auto &v : adj[u]) {
parent[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > sz[adj[u][0]]) {
std::swap(v, adj[u][0]);
}
}
}
void dfs2(int u) {
in[u] = dfs_clock++;
seq[in[u]] = u;
for (auto v : adj[u]) {
top[v] = v == adj[u][0] ? top[u] : v;
dfs2(v);
}
out[u] = dfs_clock;
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
// jump from u to k-th ancester
int jump(int u, int k) {
if (dep[u] < k) {
return -1;
}
int d = dep[u] - k;
while (dep[top[u]] > d) {
u = parent[top[u]];
}
return seq[in[u] - dep[u] + d];
}
// check if u is ancester of v (include u == v)
bool isAncester(int u, int v) {
return in[u] <= in[v] && in[v] < out[u];
}
// root is u, find parent of v
int rootedParent(int u, int v) {
std::swap(u, v);
if (u == v) {
return u;
}
if (!isAncester(u, v)) {
return parent[u];
}
auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
return in[x] < in[y];
}) - 1;
return *it;
}
// root is u, find size of subtree rooted at v
int rootedSize(int u, int v) {
if (u == v) {
return n;
}
if (!isAncester(v, u)) {
return sz[v];
}
return n - sz[rootedParent(u, v)];
}
// find the middle point of a, b, c
int rootedLca(int a, int b, int c) {
return lca(a, b) ^ lca(b, c) ^ lca(c, a);
}
};
void solve(){
int n;
std::cin >> n;
HLD hld(n);
int a, b, c;
std::cin >> a >> b >> c;
a--, b--, c--;
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
hld.addEdge(u - 1, v - 1);
}
hld.work();
while(true) {
if (hld.dist(a, c) <= 1) {
std::cout << "A\n";
return;
}
int na = hld.rootedParent(c, a);
if (hld.dist(na, b) <= 1) {
na = a;
}
if (hld.dist(na, b) <= 1) {
std::cout << "B\n";
return;
}
int nb = hld.rootedParent(na, b);
if (hld.dist(nb, c) <= 1) {
nb = b;
}
if (hld.dist(nb, c) <= 1) {
std::cout << "C\n";
return;
}
int nc = hld.rootedParent(nb, c);
if (hld.dist(nc, na) <= 1) {
nc = c;
}
if (na == a && nb == b && nc == c) {
std::cout << "DRAW\n";
return;
}
a = na;
b = nb;
c = nc;
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T;
std::cin >> T;
while(T--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A DRAW
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 19ms
memory: 3608kb
input:
10000 20 2 12 1 16 15 3 2 16 17 14 13 11 12 9 8 10 9 18 17 6 5 18 19 13 12 5 4 7 6 20 19 14 15 3 4 11 10 1 2 8 7 20 12 13 1 18 13 12 11 19 15 17 16 10 14 4 2 15 11 6 5 3 2 4 13 20 8 11 9 3 7 14 16 5 8 5 4 9 6 10 3 1 2 17 2 17 15 9 10 5 4 9 8 2 11 6 7 8 7 13 4 2 3 6 15 5 6 17 8 2 1 3 4 16 7 14 5 3 12...
output:
A B C B DRAW C A A A DRAW C B B B DRAW A DRAW A C DRAW A B A A A B B B C A A A B B DRAW C DRAW A A A A A B B A C DRAW A B A B DRAW A C DRAW A B C DRAW DRAW A A A DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B A C DRAW A B A A A B B B A A B B A C DRAW B A B A A A C A A DRAW A A C A DRAW C A B A...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 30ms
memory: 3928kb
input:
100 2000 455 1301 981 1508 1509 1242 1243 1261 1260 190 191 1981 1980 591 592 1792 1791 1726 1727 959 960 134 135 1193 1192 836 835 1803 1804 1577 1578 1548 1549 718 717 1294 1295 1116 1117 59 58 138 139 425 426 1168 1169 1963 1962 1025 1026 867 866 892 893 589 588 871 872 891 892 722 721 1711 1712 ...
output:
C A A B DRAW C A B B DRAW B C B A DRAW B C A C DRAW C B A C DRAW A C C C DRAW B A A C DRAW C A B C DRAW B A B A DRAW A C B A DRAW B C C C DRAW A B B C DRAW C B C A DRAW A C B A DRAW B A B A DRAW C A C B DRAW A B C C DRAW C B C A DRAW B A C B DRAW A A A C DRAW
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 62ms
memory: 35232kb
input:
1 200000 123236 117321 150583 47722 47723 103604 103605 48192 48191 19204 19205 3666 3667 190708 190709 111542 111541 16125 16124 164298 164299 55406 55405 62042 62041 42100 42101 40664 40663 131742 131743 105518 105517 24249 24250 174387 174388 29840 29841 164536 164537 54802 54803 6378 6377 97486 ...
output:
A
result:
ok single line: 'A'
Test #5:
score: 0
Accepted
time: 72ms
memory: 19488kb
input:
1 200000 151854 28266 141391 178840 177656 70949 127572 92675 174074 38426 55569 16718 64264 72596 171817 36908 36081 44793 65081 114199 93358 10460 36725 18563 26764 77047 29901 17769 39712 109495 141203 24130 37855 165153 135141 94225 107789 57603 49313 197306 48518 61030 57058 199291 42676 60161 ...
output:
B
result:
ok single line: 'B'
Test #6:
score: 0
Accepted
time: 63ms
memory: 27312kb
input:
1 200000 107496 54564 62204 75611 75612 33562 133562 66786 66785 35079 35078 40044 40045 99675 199675 121963 21963 15671 15672 3062 103062 71627 171627 27125 127125 30049 30048 63164 63165 183373 83373 51319 51320 99879 199879 36383 136383 89110 89109 7607 107607 20098 20099 57792 157792 100415 415 ...
output:
B
result:
ok single line: 'B'
Test #7:
score: 0
Accepted
time: 54ms
memory: 19696kb
input:
1 200000 158505 85726 178357 30247 29809 107160 107392 84411 84297 80963 81018 64893 65118 194706 194894 8253 8478 47677 48197 120341 120487 68388 68653 41048 40580 128093 127913 118156 117983 97582 97422 166508 166267 171977 171895 108683 108912 102410 102283 130584 130479 75441 75592 145257 145092...
output:
A
result:
ok single line: 'A'
Test #8:
score: 0
Accepted
time: 14ms
memory: 3580kb
input:
10992 3 1 2 3 2 1 3 1 3 1 3 2 2 1 3 1 3 2 1 3 2 1 3 1 3 2 3 1 2 1 3 1 3 3 1 2 2 1 3 1 3 3 2 1 2 1 3 1 4 1 2 3 2 1 3 2 4 1 4 1 2 4 2 1 3 2 4 1 4 1 3 2 2 1 3 2 4 1 4 1 3 4 2 1 3 2 4 1 4 1 4 2 2 1 3 2 4 1 4 1 4 3 2 1 3 2 4 1 4 2 1 3 2 1 3 2 4 1 4 2 1 4 2 1 3 2 4 1 4 2 3 1 2 1 3 2 4 1 4 2 3 4 2 1 3 2 4 ...
output:
A A B A B A B A A A A A A B A A A A A B B B C A B B A B A C A A A A A A B B A DRAW A DRAW B B A DRAW A DRAW B B A DRAW A DRAW B A A A A A A A B A A A A B B A A A A A B A A C A B B B B B C A B C A C B B A A B A A C A A A A B B A C B A C C A B B B B A A A A A A A A A A A A B B A A A A A DRAW A A DRAW ...
result:
ok 10992 lines
Test #9:
score: 0
Accepted
time: 26ms
memory: 3644kb
input:
22222 9 1 2 3 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 4 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 5 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 6 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 7 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 8 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 9 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 3 2 2 1 3 ...
output:
B B B A A A A A B B A A A A A C B A A A A A C C A A A A A A A A B B B A A A A A B B A A A A A C B A A A A A C C A A A B B B B A B B A A A A A A B A A A A A A C A A A A A A A A B B B A A A A C B B A A A A C C B A A A A C C C A A A B B B B B A A B B B B A A B A A A A A A A A A A A C A A A B B B C A A ...
result:
ok 22222 lines
Extra Test:
score: 0
Extra Test Passed