QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378359#8575. Three Person Tree Gameucup-team635#AC ✓45ms31844kbRust9.4kb2024-04-06 11:58:032024-04-06 11:58:03

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 11:58:03]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:31844kb
  • [2024-04-06 11:58:03]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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