QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378359 | #8575. Three Person Tree Game | ucup-team635# | AC ✓ | 45ms | 31844kb | Rust | 9.4kb | 2024-04-06 11:58:03 | 2024-04-06 11:58:03 |
Judging History
answer
// ---------- begin Heavy-Light decomposition ----------
pub struct HLD {
size: usize,
edge: Vec<(usize, usize)>,
child: Vec<Vec<usize>>,
path_root: Vec<usize>,
parent: Vec<usize>,
left: Vec<usize>,
right: Vec<usize>,
inverse: Vec<usize>,
}
impl HLD {
pub fn new(size: usize) -> Self {
assert!(size <= 10usize.pow(8));
HLD {
size: size,
edge: Vec::with_capacity(size - 1),
child: Vec::new(),
path_root: Vec::new(),
parent: Vec::new(),
left: Vec::new(),
right: Vec::new(),
inverse: Vec::new(),
}
}
pub fn add_edge(&mut self, a: usize, b: usize) {
assert!(a != b && a < self.size && b < self.size);
self.edge.push((a, b));
}
pub fn build(&mut self, root: usize) {
assert!(self.edge.len() + 1 == self.size);
let size = self.size;
let mut cnt = vec![0; size];
for &(a, b) in self.edge.iter() {
cnt[a] += 1;
cnt[b] += 1;
}
let mut child = cnt
.into_iter()
.map(|c| Vec::with_capacity(c))
.collect::<Vec<_>>();
for &(a, b) in self.edge.iter() {
child[a].push(b);
child[b].push(a);
}
let mut parent = vec![size; size];
let mut q = Vec::with_capacity(size);
q.push(root);
parent[root] = root;
for i in 0..size {
let v = q[i];
for u in child[v].clone() {
assert!(parent[u] == size);
parent[u] = v;
child[u].retain(|e| *e != v);
q.push(u);
}
}
let mut sum = vec![1; size];
for &v in q.iter().rev() {
let child = &mut child[v];
if !child.is_empty() {
let (pos, _) = child.iter().enumerate().max_by_key(|p| sum[*p.1]).unwrap();
child.swap(0, pos);
sum[v] = 1 + child.iter().fold(0, |s, a| s + sum[*a]);
}
}
let mut path_root = (0..size).collect::<Vec<_>>();
let mut left = vec![0; size];
let mut right = vec![0; size];
let mut dfs = vec![(root, false)];
let mut id = 0;
while let Some((v, end)) = dfs.pop() {
if end {
right[v] = id;
continue;
}
left[v] = id;
id += 1;
dfs.push((v, true));
let child = &child[v];
if !child.is_empty() {
for &u in child[1..].iter() {
path_root[u] = u;
dfs.push((u, false));
}
let u = child[0];
path_root[u] = path_root[v];
dfs.push((u, false));
}
}
let mut inverse = vec![size; size];
for (i, l) in left.iter().enumerate() {
inverse[*l] = i;
}
self.child = child;
self.parent = parent;
self.left = left;
self.right = right;
self.path_root = path_root;
self.inverse = inverse;
}
pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
assert!(a < self.size && b < self.size);
let path = &self.path_root;
let parent = &self.parent;
let index = &self.left;
while path[a] != path[b] {
if index[a] > index[b] {
std::mem::swap(&mut a, &mut b);
}
b = parent[path[b]];
}
std::cmp::min((index[a], a), (index[b], b)).1
}
pub fn path(
&self,
src: usize,
dst: usize,
up: &mut Vec<(usize, usize)>,
down: &mut Vec<(usize, usize)>,
) {
assert!(src < self.size && dst < self.size);
up.clear();
down.clear();
let path = &self.path_root;
let parent = &self.parent;
let index = &self.left;
let mut x = src;
let mut y = dst;
while path[x] != path[y] {
if index[x] > index[y] {
let p = path[x];
assert!(p == path[p]);
up.push((index[p], index[x] + 1));
x = parent[p];
} else {
let p = path[y];
assert!(p == path[p]);
down.push((index[p], index[y] + 1));
y = parent[p];
}
}
if index[x] <= index[y] {
down.push((index[x], index[y] + 1));
} else {
up.push((index[y], index[x] + 1));
}
down.reverse();
}
pub fn sub_tree(&self, v: usize) -> (usize, usize) {
assert!(v < self.size);
(self.left[v], self.right[v])
}
pub fn parent(&self, v: usize) -> Option<usize> {
assert!(v < self.size);
let p = self.parent[v];
if p == v {
None
} else {
Some(p)
}
}
// s -> t へのパスの2番目の頂点を返す
pub fn next(&self, s: usize, t: usize) -> usize {
assert!(s < self.size && t < self.size && s != t);
let (a, b) = self.sub_tree(s);
let (c, d) = self.sub_tree(t);
if !(a <= c && d <= b) {
return self.parent[s];
}
let mut pos = t;
let mut pre = t;
while self.path_root[s] != self.path_root[pos] {
pre = self.path_root[pos];
pos = self.parent[pre];
}
if s == pos {
pre
} else {
self.child[s][0]
}
}
pub fn vertex(&self, x: usize) -> usize {
assert!(x < self.size);
self.inverse[x]
}
pub fn jump(
&self,
s: usize,
t: usize,
mut k: usize,
up: &mut Vec<(usize, usize)>,
down: &mut Vec<(usize, usize)>,
) -> Option<usize> {
assert!(s.max(t) < self.size);
self.path(s, t, up, down);
for (l, r) in up.drain(..) {
if k < r - l {
return Some(self.vertex(r - 1 - k));
}
k -= r - l;
}
for (l, r) in down.drain(..) {
if k < r - l {
return Some(self.vertex(l + k));
}
k -= r - l;
}
None
}
}
// ---------- end Heavy-Light decomposition ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
// ---------- end scannner ----------
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
run(&mut sc, &mut out);
}
fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
let t: u32 = sc.next();
for _ in 0..t {
let n: usize = sc.next();
let a = sc.next::<usize>() - 1;
let b = sc.next::<usize>() - 1;
let c = sc.next::<usize>() - 1;
let mut hld = HLD::new(n);
for _ in 1..n {
let a = sc.next::<usize>() - 1;
let b = sc.next::<usize>() - 1;
hld.add_edge(a, b);
}
hld.build(0);
let mut up = vec![];
let mut down = vec![];
let mut dist = |x: usize, y: usize| -> usize {
hld.path(x, y, &mut up, &mut down);
up.iter()
.chain(down.iter())
.map(|p| p.1 - p.0)
.sum::<usize>()
- 1
};
let ans = (|| {
if dist(a, c) == 1 {
return "A";
}
let mid = hld.lca(a, b) ^ hld.lca(b, c) ^ hld.lca(c, a);
if mid == a {
return "A";
}
if mid == b {
return "B";
}
if mid == c {
return "C";
}
let x = dist(a, mid);
let y = dist(b, mid);
let z = dist(c, mid);
if x <= z + 1 && x < y {
return "A";
}
if y <= x && y < z {
return "B";
}
if z <= y && z + 1 < x {
return "C";
}
"DRAW"
})();
writeln!(out, "{}", ans).ok();
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 2060kb
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: 2632kb
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: 22ms
memory: 3964kb
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: 22ms
memory: 31844kb
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: 45ms
memory: 28664kb
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: 26ms
memory: 31744kb
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: 29ms
memory: 28908kb
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: 9ms
memory: 2376kb
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: 20ms
memory: 2864kb
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