Educational Codeforces Round #105 Dogeforces - 并查集 + 构造

题意

有一家公司,出了最底层员工,每个员工至少有个2个下属,且其工资一定严格高于其下属。

现在给你$n$个底层员工。以及任意两个员工的最近的公共上司的工资。要你构造出这个公司的整体结构。

题解

直接对上司的工资排序。(可怕~)

也就是根据value进行排序。

static class Node {
    int x, y, value;
}

我们维护一个动态的并查集。一开始,只有$n$个员工在里面,这$n$个员工的父亲是空(注意,不是自己。)

因为工资是排过序的。所以按工资顺序,依次将node.xnode.y放到一个集合里是合理的。

如果$x$往上和$y$往上最大的boss的工资一样,且这个工资恰好等于node.value。那说明两个人本来就是一个boss。

如果两个中,只有一个boss的工资等于value。那么说明,另一个boss应该是这个boss的下属。

再如果,如果这两个boss的工资都小于value。那么说明这两个boss的直接上司的工资是node.value。于是我们在并查集里创建一个新的员工,且这个员工的工资是node.value,且这个员工是那两个boss的boss。

代码

Submission #114386442 - Codeforces
Codeforces. Programming competitions and contests, programming community