比赛场次 | 614 |
---|---|
比赛名称 | 2024暑期C班集训4 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-07-04 08:00:00 |
结束时间 | 2024-07-04 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | 3 + 1 |
题目名称 | 飘雪圣域 |
---|---|
输入输出 | icekingdom.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
yrtiop | AAAAAAAAAA | 0.712 s | 8.53 MiB | 100 |
小金 | AAAAAWWWWW | 0.080 s | 2.30 MiB | 50 |
健康铀 | AAAAAEEEEE | 1.068 s | 33.07 MiB | 50 |
liuyiche | AAAAATTTTT | 5.000 s | 8.20 MiB | 50 |
darkMoon | AAAAATTTTT | 5.009 s | 15.06 MiB | 50 |
dream | AAAAATTTTT | 5.048 s | 6.15 MiB | 50 |
Untitled | AAAAATTTTT | 5.157 s | 7.22 MiB | 50 |
wzh0425 | AAAAATTTTT | 5.187 s | 6.15 MiB | 50 |
djyqjy | AAAAATTTTT | 5.220 s | 7.22 MiB | 50 |
AeeE5x | AAAAATTTTT | 5.256 s | 9.28 MiB | 50 |
彭欣越 | AAAAATTTTT | 5.320 s | 11.84 MiB | 50 |
123 | AAAAATTTTT | 5.374 s | 10.65 MiB | 50 |
wdsjl | AAAWWEEEEE | 1.009 s | 6.06 MiB | 30 |
flyfree | C | 0.000 s | 0.00 MiB | 0 |
IcePrincess_1968 和 IcePrince_ 1968 长大了,他们开始协助国王 IceKing_1968 管理国内事物。
IcePrincess_1968 和 IcePrince_ 1968 住在一个宁静悠远的王国:IceKingdom —— 飘雪圣域。飘雪圣域有 n 个城镇,编号 1,2,3...n。有些城镇之间有道路,且满足任意两点之间有且仅有一条路径。飘雪圣域风景优美,但气候并不是太好。根据 IcePrince_1968 的气候探测仪,将来会发生 q 场暴风雪。每场暴风雪可以用两个整数 li,ri 刻画,表示这场暴风雪之后,只有编号属于[li,ri]的城市没有受到暴风雪的影响。
在暴风雪的影响下迅速确定王国的农业生产方案是非常重要的事情。IceKing_1968 认为,一个农业生产地域应该是一个极大连通块,满足每个节点都没有被暴风雪影响。这里极大连通块的定义是:不存在一个不属于该点集的未被暴风雪影响的点与该连通块连通。
IcePrincess_1968 要负责算出每次暴风雪后,王国能拥有多少个农业生产地域。注意这里每次暴风雪是独立的,即每次暴风雪过后,直到每个城镇重新焕发生机,下一次暴风雪才会到来。
正如上文所述,IcePrincess_1968 擅长文学但不擅长计算机,于是请你帮忙。
第一行包含两个正整数 n,q,表示 IceKingdom 的城镇个数和暴风雪次数
第 2 至第 n 行,每行两个正整数 x,y,表示城镇 x 和城镇 y 之间有一条道路
第 n+1 至第 n+q 行,每行两个正整数 li,ri,描述一场暴风雪,含义如题面所述。
输出文件共有 q 行,第 i 行表示在第 i 场暴风雪之后农业生产地域的个数。
4 3 1 2 2 3 2 4 1 2 1 3 3 4
1 1 2
第一次询问,只有(1,2)一个连通块。
第二次询问,只有(1,2,3)一个连通块。
第三次询问,有 3 和 4 两个连通块。
对于 30%的数据:n<=100,q<=100;
对于 50%的数据:n<=2,000,q<=2,000;
对于 100%的数据:n<=200,000,q<=200,000,对于所有的暴风雪,li<=ri。