广东腾越建筑工程有限公司,企业seo推广外包,老榕树网站建设教学,网站建设需要注意的题目链接#xff1a;Vlad and the Mountains
由题意我们可知#xff0c;从u到v不管怎么走#xff0c;山的高度始终不能超过h(st)e#xff0c;那么问题就转化为了给定q次询问#xff0c;是否存在一条路径#xff0c;使得从u到v的所有点的高度不超过h(u)e。那么就可以考虑…题目链接Vlad and the Mountains
由题意我们可知从u到v不管怎么走山的高度始终不能超过h(st)e那么问题就转化为了给定q次询问是否存在一条路径使得从u到v的所有点的高度不超过h(u)e。那么就可以考虑并查集将所有点h(u)e合并然后判断是否连通。
那么一次次枚举询问显然会超时那么可以采用离线询问的方式去解决
首先记录每次询问然后根据h(u)e的大小从小到大排序同时对山峰的高度进行排序那么高度从小到大将一个个点连通不影响结果。
代码附上
#include bits/stdc.h
#define int long long
using namespace std;
const int N 2e55;
int h[N],b[N],pre[N],ans[N],vis[N];
vectorintg[N];
struct node{int u,v,e,id;
}q[N];
int n,m,que;int cmp(node a,node b){return h[a.u]a.eh[b.u]b.e;
}int cmp1(int a,int b){return h[a]h[b];
}int root(int x){return pre[x](pre[x]x)?x:root(pre[x]);
}void init(){for(int i1;in;i){pre[i]i;b[i]i;g[i].clear();h[i]ans[i]vis[i]0;}
}void solve(){cinnm;init();for(int i1;in;i)cinh[i];for(int i1;im;i){int x,y;cinxy;g[x].push_back(y);g[y].push_back(x);}cinque;for(int i1;ique;i){//离线询问cinq[i].uq[i].vq[i].e;q[i].idi;}sort(q1,q1que,cmp);//对询问的初始高度排序sort(b1,b1n,cmp1);//对山峰的高度排序索引int j1;for(int i1;ique;i){for(;jn;j){if(h[b[j]]h[q[i].u]q[i].e)break;//如果高度超出vis[b[j]]1;for(const auto y:g[b[j]]){//判断两点是否能连通if(vis[y]){int fxroot(b[j]);int fyroot(y);if(fx!fy)pre[fx]fy;}}}ans[q[i].id](root(q[i].u)root(q[i].v));}for(int i1;ique;i){if(ans[i])coutYES\n;else coutNO\n;}cout\n;return;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cint;while(t--){solve();}return 0;
}
