这玩意在 uoj 老哥的毒瘤数据上 MLE 了……
思路就是普通的 kdt 优化建图+隐式建图+铃的剪枝
死活看不出来哪里可以 MLE
#include<algorithm>
#include<queue>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-') c=getchar();
if(c=='-'){
f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=7e4+5,maxm=1.5e5+5;
int n,m,x[maxn],y[maxn],t[maxm],L[maxm],R[maxm],D[maxm],U[maxm];
vector<int> p[maxn];
int rt,ch[maxn][2],mnx[maxn],mny[maxn],mxx[maxn],mxy[maxn],ord[maxn];
bool cmp1(int a,int b){
return x[a]<x[b];
}
bool cmp2(int a,int b){
return y[a]<y[b];
}
void pushup(int o){
mnx[o]=mxx[o]=x[o];
mny[o]=mxy[o]=y[o];
if(ch[o][0]){
mnx[o]=min(mnx[o],mnx[ch[o][0]]);
mxx[o]=max(mxx[o],mxx[ch[o][0]]);
mny[o]=min(mny[o],mny[ch[o][0]]);
mxy[o]=max(mxy[o],mxy[ch[o][0]]);
}
if(ch[o][1]){
mnx[o]=min(mnx[o],mnx[ch[o][1]]);
mxx[o]=max(mxx[o],mxx[ch[o][1]]);
mny[o]=min(mny[o],mny[ch[o][1]]);
mxy[o]=max(mxy[o],mxy[ch[o][1]]);
}
}
int build(int l,int r,bool d){
if(l==r){
pushup(ord[r]);
return ord[r];
}
if(l+1==r){
ch[ord[l]][1]=ord[r];
pushup(ord[r]);
pushup(ord[l]);
return ord[l];
}
int mid=l+(r-l)/2;
nth_element(ord+l,ord+mid,ord+r+1,d?cmp1:cmp2);
ch[ord[mid]][0]=build(l,mid-1,!d);
ch[ord[mid]][1]=build(mid+1,r,!d);
pushup(ord[mid]);
return ord[mid];
}
int dis[maxn*2];
void query(int o,int l,int r,int d,int u,vector<int>& res,int now){
if(dis[o+n]<=now) return;
if(l<=mnx[o]&&r>=mxx[o]&&d<=mny[o]&&u>=mxy[o]){
res.push_back(o+n);
return;
}
if(l<=x[o]&&r>=x[o]&&d<=y[o]&&u>=y[o]) res.push_back(o);
int lc=ch[o][0],rc=ch[o][1];
if(lc&&l<=mxx[lc]&&r>=mnx[lc]&&d<=mxy[lc]&&u>=mny[lc])
query(lc,l,r,d,u,res,now);
if(rc&&l<=mxx[rc]&&r>=mnx[rc]&&d<=mxy[rc]&&u>=mny[rc])
query(rc,l,r,d,u,res,now);
}
bool vis[maxn*2];
typedef pair<int,int> pii;
const int inf=2e9;
void dijkstra(){
for(int i=1;i<=n*2;i++) dis[i]=inf;
priority_queue<pii,vector<pii>,greater<pii> > pq;
dis[1]=0;
pq.push(pii(0,1));
while(!pq.empty()){
int u=pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
if(u<=n) for(int i=0;i<(int)p[u].size();i++){
int v=p[u][i];
vector<int> res;
if(L[v]<=mxx[rt]&&R[v]>=mnx[rt]&&D[v]<=mxy[rt]&&U[v]>=mny[rt])
query(rt,L[v],R[v],D[v],U[v],res,dis[u]+t[v]);
for(int j=0;j<(int)res.size();j++) if(dis[res[j]]>dis[u]+t[v]){
dis[res[j]]=dis[u]+t[v];
pq.push(pii(dis[res[j]],res[j]));
}
}
else{
if(ch[u-n][0]&&dis[ch[u-n][0]+n]>dis[u]){
dis[ch[u-n][0]+n]=dis[u];
pq.push(pii(dis[ch[u-n][0]+n],ch[u-n][0]+n));
}
if(ch[u-n][1]&&dis[ch[u-n][1]+n]>dis[u]){
dis[ch[u-n][1]+n]=dis[u];
pq.push(pii(dis[ch[u-n][1]+n],ch[u-n][1]+n));
}
if(dis[u-n]>dis[u]){
dis[u-n]=dis[u];
pq.push(pii(dis[u-n],u-n));
}
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
n=readint();
m=readint();
readint();
readint();
for(int i=1;i<=n;i++){
x[i]=readint();
y[i]=readint();
}
for(int i=0;i<m;i++){
p[readint()].push_back(i);
t[i]=readint();
L[i]=readint();
R[i]=readint();
D[i]=readint();
U[i]=readint();
}
for(int i=1;i<=n;i++) ord[i]=i;
rt=build(1,n,0);
dijkstra();
for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
return 0;
}
``