P5068 [Ynoi2015]我回来了

    • 179通过
    • 464提交
  • 题目提供者 noip 毒瘤
  • 评测方式 云端评测
  • 标签 2015 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    我遵守了...
    约...约定

    【你非常努力啊】
    我非常非常努力哦...

    【虽然昨天也说过这句话了...】
    【欢迎回来,珂朵莉】

    我回来了...
    终于说出口了...
    【是啊,我终于听见了】
    红色的头发,会不会奇怪?
    【很漂亮的颜色,和你很搭哦】
    是吗...
    我...我已经没事了
    【真的吗?身体状况没问题吗?】
    【要是硬撑的话,我可不会饶过你啊】
    没事的,做饭啊洗衣服啊,还留着很多活要干呢
    【可别太拼了哦】

    哼,你就做好心理准备等着吧

    题目描述

    珂朵莉给你一个无向图,每次查询的时候给一堆二元组(xi,yi)
    求图中有多少个点u与至少一个这次询问给出的二元组(xi,yi)满足 dist(u,xi)<=yi,dist表示这两个点在图中的距离
    如果不连通dist = inf

    输入输出格式

    输入格式:

    第一行三个数表示n,m,q
    n表示顶点个数,m表示边数
    之后m行每行两个数x,y表示这两个点之间连有一条边~,边权都为1
    之后q次询问,每个询问先给你一个数a
    之后a行每行两个数,x,y,表示一个二元组
    n <= 1000 , m <= 100000 , q <= 100000
    a的和 <= 2100000

    输出格式:

    q行,每行一个数表示这次询问的答案

    输入输出样例

    输入样例#1: 复制
    5 6 6
    2 3
    1 3
    2 5
    1 3
    3 2
    2 5
    1
    3 1
    1
    1 1
    1
    1 4
    1	
    5 2
    1
    1 4
    2
    1 0
    5 1
    输出样例#1: 复制
    3
    2
    4
    3
    4
    3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。