#PQJ934x4061. QOJ 934_4061

    ID: 3071 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2022并查集

QOJ 934_4061

2022 年陕西省NOI 省队选拔赛试题 垃圾回收(garbage) 垃圾回收(garbage) 【题目描述】 通常的情况下,编程语言在管理内存时会进行如下的选择: • 让用户进行手动内存管理(C,C++,Rust 等),这会收获很好的性能,但是给用户提供 了很大的编程负担。 • 使用垃圾回收系统(Java,Go 等),这需要维护一个运行时系统,并且在内存使用和程序 性能方面造成了许多不可预测的负担。 尽管存在许多的问题,目前最通用的自动化内存管理手段始终为Tracing Garbage Collec- tor。这种做法的最基础的思路是维护对象间的引用关系,形成一张图,每次回收时通过扫描引 用关系推导出已经无法被访问到的对象,释放它们占用的内存。而这种传统的做法最大的问题 在于维护引用链需要造成很大的开销,并且随着维护的对象越多,扫描的代价也会越大。 小L 是一个喜欢思考的女孩子,她发现维护Garbage Collector 是一件非常复杂的事情,于 是她决定考虑一个更简单的模型(注意它与任何现实中的GC 规则可能是完全不同的!)。 对于一个n 个点m 条边的无向图,没有重边自环,点和边均从1 开始标号。其中每个节点 代表一个占用了一定内存的对象,每条边对应一个引用关系(注意这里的引用关系是.无.向的), 程序从第0 秒开始运行,在第q + 1 秒结束运行。对于i = 1, 2, 3, ..., q 的每个时刻i ,程序会 进行以下两种操作之一: • DELETE i, 删除边(xi, yi) ,保证不会删除已经被删除的边。 • GC, 进行一次内存回收,即杀死所有从1 号点出发不能访问到的点,释放它们占用的内 存。(注意这里对节点的删除不会删除与这些点相连的边) 你可以认为这些操作是被瞬间执行完成的,在所有操作执行后,也就是第q + 1 秒,程序 结束,删除所有剩余的节点(包括1 号点)。 第i 个节点占用的内存为ai。现在请你求出整个程序的开销,即∑n i=1 ai · ti,这里ti 表示 第i 个点存活的时间,在第0 秒,所有节点都是存活的。 【输入格式】 从文件garbage.in 中读入数据。 输入的第一行是三个正整数n, m, q,分别表示对象的个数,引用关系的个数,操作的个数。 接下来m 行,每行2 个正整数xi, yi 表示第i 条引用关系的两个端点。 接下来q 行,每行为以下两种形式之一,第i 行表示程序在第i 秒进行的操作: • 一个字符串DELETE 和一个正整数x, 含义见【题目描述】。 • 一个字符串GC,含义见【题目描述】。 接下来的一行有n 个正整数a1, a2, . . . , an,表示每个对象占用的内存大小。 第2 页,共13 页

2022 年陕西省NOI 省队选拔赛试题 垃圾回收(garbage) 【输出格式】 输出到文件garbage.out 中。 输出一行一个整数表示程序的开销,含义见【题目描述】。 【样例输入1】 见选手目录下的garbage/garbage1.in。 6 6 8 1 2 2 3 2 4 1 4 2 5 1 6 GC DELETE 5 DELETE 3 GC DELETE 1 GC DELETE 2 GC 1 2 3 4 5 6 【样例输出1】 见选手目录下的garbage/garbage1.ans。 149 【样例解释1】 在第4 秒时,节点5 被删除。 在第6 秒时,节点2, 3 被删除。 在第9 秒时,节点1, 4, 6 被删除。 因此。程序的开销为5 × 4 + (2 + 3) × 6 + (1 + 4 + 6) × 9 = 20 + 30 + 99 = 149。 【样例2】 见选手目录下的garbage/garbage2.in 和garbage/garbage2.ans。 本组数据满足测试点6 的限制。 第3 页,共13 页

2022 年陕西省NOI 省队选拔赛试题 垃圾回收(garbage) 【样例3】 见选手目录下的garbage/garbage3.in 和garbage/garbage3.ans。 本组数据满足测试点11 的限制。 【数据规模与约定】 对于全部数据,1 ≤n, m, q ≤4 × 105,1 ≤ai ≤108。 具体的数据规模与约定见下表。 测试点编号 n m q 特殊约定 1 ∼2 ≤500 ≤500 ≤500 无 3 ∼5 ≤3000 ≤3000 ≤3000 6 ∼10 ≤5000 ≤5000 ≤5000 11 ∼14 ≤2 × 105 n −1 ≤2 × 105 保证一开始图是一棵树 15 ∼16 ≤2 × 105 ≤2 × 105 ≤2 × 105 无 17 ∼20 ≤4 × 105 ≤4 × 105 ≤4 × 105 第4 页,共13 页