题目描述

Description

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

Input

第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。

Output

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

Sample Input

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

Sample Output

6
1
-1
8

HINT

【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

题目分析

可以离线
将边按边权排序 用并查集维护点的连通性 每个联通块维护一颗权值线段树
离线询问 按询问的权值大小排序 对于每个询问 把所有小于等于询问权值的边加入并查集，并合并两个联通块的权值线段树 之后在包含x的联通块的权值线段树里查询第k大即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
struct your
{
    int x,y,c,id;
}edge[500010],q[500010];
struct my
{
    int lson,rson,size;
}a[5000100];
int root[500100],tot,val[100010],f[100010];
int cmp(your j,your k) { return j.c<k.c; }
int cmp2(your j,your k) { return j.y<k.y; }
int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
void build(int dx,int l,int r,int &x)
{
    if(!x) x=++tot;
    if(l==r) { a[x].size=1; return ; }
    int mid=(l+r)>>1;
    if(dx<=mid) build(dx,l,mid,a[x].lson);
    else build(dx,mid+1,r,a[x].rson);
    a[x].size=a[a[x].lson].size+a[a[x].rson].size; 
}
void merge(int &x,int y,int l,int r)
{
    if(!x||!y) { x=x+y; return ; }
    if(l==r) { a[x].size+=a[y].size; return ; }
    int mid=(l+r)>>1;
    merge(a[x].lson,a[y].lson,l,mid),merge(a[x].rson,a[y].rson,mid+1,r);
    a[x].size=a[a[x].lson].size+a[a[x].rson].size;
}
int ask(int l,int r,int num,int x)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(a[a[x].rson].size>=num) return ask(mid+1,r,num,a[x].rson);
    else return ask(l,mid,num-a[a[x].rson].size,a[x].lson);
}
int ans[500010];
void work()
{
    for(int i=1;i<=n;i++) build(val[i],1,1000000000,root[i]);
    for(int now=1,i=1;i<=k;i++)
    {
        while(now<=m&&edge[now].c<=q[i].y) 
        {
            int dx=find(edge[now].x),dy=find(edge[now].y);
            if(dx!=dy) f[dy]=dx,merge(root[dx],root[dy],1,1000000000);
            now++;
        }
        int rot=find(q[i].x);
        if(a[root[rot]].size>=q[i].c)
            ans[q[i].id]=ask(1,1000000000,q[i].c,root[rot]);
        else ans[q[i].id]=-1;   
    }
}
int main()
{   
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].c);
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=k;i++) scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].c),q[i].id=i; 
    sort(q+1,q+k+1,cmp2),work();
    for(int i=1;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}