| 题目名称 | 419. [IOI 2009]区域发展 |
|---|---|
| 输入输出 | region.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 8000 ms (8 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 33 |
| 题目来源 |
 cqw
于2010-04-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：11， 提交：82， 通过率：13.41% | ||||
 j31234 |
100 | 7.210 s | 252.57 MiB | C++ |
 ceerRep |
100 | 7.769 s | 103.35 MiB | C++ |
 FoolMike |
100 | 8.970 s | 106.20 MiB | C++ |
 cstdio |
100 | 11.614 s | 103.35 MiB | C++ |
 Rivendell |
100 | 20.692 s | 5.67 MiB | C++ |
 fye |
100 | 22.251 s | 6.61 MiB | C++ |
 lcomyn |
100 | 22.518 s | 6.41 MiB | C++ |
 Asm.Def |
100 | 24.458 s | 82.53 MiB | C++ |
 TA |
100 | 25.199 s | 7.94 MiB | C++ |
|
Asm.Def |
100 | 36.921 s | 8.96 MiB | C++ |
| 关于 区域发展 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Asm.Def :
orz夹心学长，同样的算法我写出来就TLE了-_- | ||||
|
回复 @TA :
我看BZOJ上的题面里有一句话：答案不超过1e9 | ||||
|
可持久化线段树+启发式计算，理论复杂度是O(n*sqrt(n)*logn)的在线算法，但是免不了TLE的命运
| ||||
|
| ||||
|
看了大神们的Code竟然都是用的int。。我有点呵呵。
TA
2015-03-30 21:51
8楼
| ||||
|
我擦我把暴力的long long改成int就A了。。这什么水数据。
TA
2015-03-30 21:49
7楼
| ||||
|
暴力就T了一个。。。
TA
2015-03-30 21:20
6楼
| ||||
|
今天晚上是怎么了……各种莫名奇妙的错误= =为何我直接递归dfs会运行错误啊卧槽……最后手工模拟了个递归栈=_=||||
第二次AC的这个版本我直接写成了括号序列，离线预处理部分（r1或r2的人数大于c的情况）利用括号序列上的线性扫描+计数（例如维护某一侧的左括号数-右括号数）可以做到O(N^2/c)，同理每次在线Query复杂度为O(|r1|+|r2|)，其实也就是O(c)。（可是我的递归dfs为什么会RE！如果是栈溢出的话为什么在本地连个segment fault都不给我= =？百思不得其解……） 唉…最后这几天专心复习期末考试吧…… | ||||
|
居然是被题解误导了= =
求神犇们教我学分块……我这个三十多秒的是dfs序列上二分查找+树上的可持久化线段树+部分扫描……TAT而且我估计我最后算的时间复杂度是错的= = | ||||
|
回复 @Asm.Def :
233333  天一阁
2015-01-20 08:42
3楼
| ||||
【题目描述】
联合国区域发展署（UNRDA）有非常清晰的组织结构。它雇佣了总共N个人，每个人都来自世界上R个不同的地区之一。员工们按照资历从1到N编号（含1，N），其中1号员工即主席有着最高的资历。R个地区被任意地从1到R编号。除主席之外的每一位员工都有一名直接上司。直接上司的资历总是比他/她手下的员工高。
我们称员工A是员工B的管理者，当且仅当A是B的直接上司，或A是B的直接上司的管理者。例如，可以发现主席是所有其他员工的管理者。并且，显然没有两名员工互为管理者。
不幸的是，联合国调查局（UNBI）最近接到了一些投诉，声称区域发展署的组织结构是不平衡的，因而会偏袒某些地区。为了调查这些指责，调查局希望建立一个计算机系统，使得给出发展署的组织结构后，能够回答一些如下格式的询问：给定两个不同的地区r1和r2，问发展署中有多少对员工e1和e2，使得e1来自地区r1，e2来自地区r2，并且e1是e2的管理者。每个询问都有两个参数：地区r1和r2，而其结果是一个整数：满足上述要求的不同(e1,e2)有多少对。
写一个程序，在给定发展署所有员工来自的地区，以及每一名员工的直接上司后，回答上述询问。
【数据规模】
1<=N<=200000 —— 雇员人数
1<=R<=25000 ——地区数量
1<=Q<=200000 —— 询问总数
1<=Hk<=R —— k号员工所来自地区（1<=k<=N）
1<=Sk<k —— k号员工的直接上司（2<=k<=N）
1<=r1，r2<=R —— 询问中的两个地区
【输入格式】
第一行三个整数：N，R，Q，用空格隔开。
接下来N行按资历顺序描述了发展署中的N名员工。N行中的第k行描述了编号为k的员工。N行中的第一行（即对于主席的描述）包含一个整数：来自地区H1.其余N-1行包含两个空格隔开的整数：直接上司Sk，来自地区Hk。
接下来的Q行包含了Q个询问，每个询问一行，两个整数r1,r2.
【输出格式】
Q行Q个整数，即Q个询问的答案。
【输入样例】
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
【输出样例】
1
3
2
1
【提示】
有30%的数据，R不超过500.
有55%的数据，员工数不超过500.
有15%的数据同时满足以上两个条件。
有70%的数据至少满足两个条件之一。
原题是强制在线的交互式题目。