QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378340 | #8575. Three Person Tree Game | ucup-team635# | WA | 19ms | 2580kb | Rust | 9.4kb | 2024-04-06 11:31:38 | 2024-04-06 11:31:39 |
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";
}
if dist(b, a) == 1 {
return "B";
}
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 && x < y {
return "A";
}
if y <= x && y < z {
return "B";
}
if z <= y && z + 1 < x {
return "C";
}
"DRAW"
})();
writeln!(out, "{}", ans).ok();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2032kb
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: -100
Wrong Answer
time: 19ms
memory: 2580kb
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 B A A B B B C A B B B B DRAW C DRAW A A A A A B B A C DRAW B 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 DRAW 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 ...
result:
wrong answer 23rd lines differ - expected: 'A', found: 'B'