luogu|luogu 5471 [NOI2019]弹跳 KDtree + Dijkstra
Code:
#include
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 2000000
#define inf 100000000
#define lson t[now].ch[0]
#define rson t[now].ch[1]
#define ll long long
using namespace std;
struct Edge {
int t,x1,y1,x2,y2;
Edge(int t=0,int x1=0,int y1=0,int x2=0,int y2=0):t(t),x1(x1),y1(y1),x2(x2),y2(y2){}
};
struct Data {
int ch[2],minv[2],maxv[2],siz,id,p[2];
}t[maxn],arr[maxn];
struct P {
int dis,id;
P(int dis=0,int id=0):dis(dis),id(id) {}
bool operator<(P b) const {
return b.disG[maxn];
priority_queueQ;
vectoredges;
int d,cnt,len;
int dis[maxn],answer[maxn],nd[maxn],vis[maxn];
void Min(int &a,int b) {
if(ba) a=b;
}
bool cmp(Data i,Data j) {
return i.p[d]==j.p[d]?i.p[d^1]>1;
d=o,nth_element(arr+l,arr+mid,arr+1+r,cmp);
build(l,mid,lson,o^1);
if(r>mid) build(mid+1,r,rson,o^1);
pushup(now),t[now].siz=t[lson].siz+t[rson].siz;
}
void dfs(int now,int x1,int y1,int x2,int y2) {
if(t[now].minv[0]>y1||t[now].maxv[0]y2||t[now].maxv[1] 【luogu|luogu 5471 [NOI2019]弹跳 KDtree + Dijkstra】
推荐阅读
- [逆元]|[逆元] luogu 4942
- 【线性求逆元板子】|【线性求逆元板子】 luogu 3811
- [exgcd算最值]|[exgcd算最值] luogu 3951
- Luogu|Luogu 5170 【模板】类欧几里得算法
- 扩展欧几里得例题(luogu_1082)
- KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）
- NOI2019|NOI2019 回家路线 DP
- LOJ|LOJ 3156: 「NOI2019」回家路线
- [NOI2019]|[NOI2019] 弹跳
- LOJ|LOJ 3159: 「NOI2019」弹跳