| 题目名称 | 2295. [HZOI 2015]榴莲 |
|---|---|
| 输入输出 | Durio_zibethinus_Murr.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：19， 提交：66， 通过率：28.79% | ||||
 FoolMike |
100 | 0.846 s | 85.17 MiB | C++ |
 gls1196 |
100 | 0.941 s | 20.53 MiB | C++ |
 zhrt |
100 | 0.957 s | 37.70 MiB | C++ |
 zhoushuyu |
100 | 0.973 s | 11.74 MiB | C++ |
 _Itachi |
100 | 0.981 s | 25.47 MiB | C++ |
|
zhrt |
100 | 0.988 s | 37.70 MiB | C++ |
|
zhrt |
100 | 0.998 s | 37.70 MiB | C++ |
 AntiLeaf |
100 | 1.137 s | 470.71 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 1.142 s | 17.07 MiB | C++ |
|
YGOI_真神名曰驴蛋蛋 |
100 | 1.156 s | 15.55 MiB | C++ |
| 关于 榴莲 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @zhoushuyu :
因为您强  sdzwyq
2018-07-31 22:28
12楼
| ||||
|
为什么这种求第k大的题目
总是不能从样例中发现自己写成了第k小啊qwq | ||||
|
回复 @Marvolo :
树剖的那个log是可以用树上差分去掉的…… AntiLeaf
2017-04-20 19:46
10楼
| ||||
|
1.7s->1.5s->1.3s->1.1s->1.02s->0.96s……
常数压得我心力憔悴…… 超级快读+各种位运算优化+线段树永久化标记…… 原来三个Log也能过…… | ||||
|
您们写整体二分的就不能考虑考虑我这个写树套树的感受嘛……
| ||||
|
sort居然比基数排序慢这么多……
清空标记居然比倒回操作快这么多…… Itachi的代码居然比我的短这么多…… bit居然比segmenttree快这么多…… 真是缺乏经验 | ||||
|
整体二分就是入魂
_Itachi
2017-02-23 18:37
6楼
| ||||
|
边表忘开2倍居然不RE
YGOI_真神名曰驴蛋蛋
2017-01-05 21:26
5楼
| ||||
|
你有信仰吗
| ||||
|
调试语句忘记删除还让我T一发……
 真呆菌
2016-10-06 10:43
3楼
| ||||
Marvolo2295. [HZOI 2015]榴莲
★★☆ 输入文件：Durio_zibethinus_Murr.in
输出文件：Durio_zibethinus_Murr.out
简单对比时间限制：1 s 内存限制：512 MiB
【题目描述】
众所周知，榴莲长在树上，同时榴莲很臭
现在给定你一棵榴莲树，树根为1
要求你维护以下操作：
1、 1 u v w 树上长出一个榴莲，臭味度为w，臭味弥漫了树上u到v的简单路径上所有点
2、 2 u w 树上长出一个榴莲，臭味度为w，臭味弥漫了树上u的子树的所有点
3、 3 k 树上k时刻长出的榴莲从树上掉了下来，它所造成的臭味效果消失
4、 4 u k 询问所有弥漫到u节点的榴莲臭味值的第k大
【输入格式】
第一行输入n，m表示节点总数和操作次数
以下n-1行u，v描述两个端点
以下m行，第i行表示第i个时刻的操作如题意所示
n,m<=100000
数据保证第三个操作掉下来的是存在的且尚未掉下来的榴莲
【输出格式】
对于每个询问
若弥漫到u节点的榴莲不足k个，则输出-1
否则输出对应的答案
【样例输入】
10 10 2 1 3 1 4 3 5 4 6 1 7 3 8 3 9 7 10 2 4 1 1 1 3 1 13881 3 2 2 10 12573 2 7 2522 1 10 7 7976 1 7 7 15696 4 2 1 1 3 4 14384 1 10 9 7398
【样例输出】
-1 7976