TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5309
  • 题目
  • P5309「ONTAK2010」Peaks加强版
    限制 : 时间限制 : 10000 MS   空间限制 : - KB
    评测说明 : 2s,164m
    问题描述

    在Bytemountains有N座山峰,每座山峰有他的高度$h_i$。
    有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。

    输入格式

    第一行三个数N,M,Q。

    第二行N个数,第i个数为$h_i $

    接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径。

    接下来Q行,每行三个数v x k,表示一组询问。v=v xor lastans,x=x xor lastans,k=k xor lastans。如果lastans=-1则不变。

    输出格式

    对于每组询问,输出一个整数表示答案。

    样例输入

    10 11 4
    1 2 3 4 5 6 7 8 9 10
    1 4 4
    2 5 3
    9 8 2
    7 8 10
    7 1 4
    6 7 1
    6 4 8
    2 1 5
    10 8 10
    3 4 7
    3 4 6
    1 5 2
    1 5 6
    1 5 8
    8 9 2

    样例输出

    6
    10
    9
    -1

    提示

    \(N<=10^5\)
    $ M,Q<=5*10^5$
    \(h_i,c,x<=10^9。\)


    来源  bzoj 3551