我知道裸的二维线段树优化建图过不了这题,但是好歹拿个 72 吧,怎么只有 32?
感觉可能是哪里实现假了
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define mkp make_pair
using namespace std;
const int maxn=2e6+7;
// 21:52-22:18
int n,m,w,h;
int pnt_tot;
vector<pair<int,int> >vec[maxn];
namespace SegT{
struct node{
int id;
int son[2][2];
}tree[10000007];
int tot;
void update(int fa,int &o,int lx,int rx,int ly,int ry,pair<int,int>pos,int id){
if(lx>rx||ly>ry)return;
if(!o){
o=++tot;
tree[o].id=++pnt_tot;
vec[tree[fa].id].emplace_back(mkp(tree[o].id,0));
}
if(lx==rx&&ly==ry){
vec[tree[o].id].emplace_back(mkp(id,0));
return;
}
int midx=lx+rx>>1,midy=ly+ry>>1;
if(pos.first<=midx&&pos.second<=midy)update(o,tree[o].son[0][0],lx,midx,ly,midy,pos,id);
if(pos.first>midx&&pos.second<=midy)update(o,tree[o].son[1][0],midx+1,rx,ly,midy,pos,id);
if(pos.first<=midx&&pos.second>midy)update(o,tree[o].son[0][1],lx,midx,midy+1,ry,pos,id);
if(pos.first>midx&&pos.second>midy)update(o,tree[o].son[1][1],midx+1,rx,midy+1,ry,pos,id);
}
void connect(int o,int lx,int rx,int ly,int ry,int qlx,int qrx,int qly,int qry,int pnt,int w){
if(!o)return;
if(lx>rx||ly>ry)return;
if(qlx<=lx&&rx<=qrx&&qly<=ly&&ry<=qry){
vec[pnt].emplace_back(mkp(tree[o].id,w));
return;
}
int midx=lx+rx>>1,midy=ly+ry>>1;
if(lx<=midx&&ly<=midy)connect(tree[o].son[0][0],lx,midx,ly,midy,qlx,qrx,qly,qry,pnt,w);
if(rx>midx&&ly<=midy)connect(tree[o].son[1][0],midx+1,rx,ly,midy,qlx,qrx,qly,qry,pnt,w);
if(lx<=midx&&ry>midy)connect(tree[o].son[0][1],lx,midx,midy+1,ry,qlx,qrx,qly,qry,pnt,w);
if(rx>midx&&ry>midy)connect(tree[o].son[1][1],midx+1,rx,midy+1,ry,qlx,qrx,qly,qry,pnt,w);
}
int root;
}
ll dis[maxn];
const ll inf=1e17;
void dijkstra(){
priority_queue<pair<ll,int> >q;
for(ri i=1;i<=pnt_tot;i++)dis[i]=inf;
dis[1]=0;
q.push(mkp(0,1));
while(!q.empty()){
int u=q.top().second;ll d=-q.top().first;q.pop();
if(d!=dis[u])continue;
for(auto [v,w]:vec[u]){
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
q.push(mkp(-dis[v],v));
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
cin>>n>>m>>w>>h;
pnt_tot=n;
for(ri i=1;i<=n;i++){
int x,y;cin>>x>>y;
SegT::update(0,SegT::root,1,w,1,h,mkp(x,y),i);
}
// cout<<pnt_tot<<endl;
for(ri i=1;i<=m;i++){
int p,t,l,r,d,u;cin>>p>>t>>l>>r>>d>>u;
SegT::connect(SegT::root,1,w,1,h,l,r,d,u,p,t);
}
dijkstra();
for(ri i=2;i<=n;i++)cout<<dis[i]<<'\n';
return 0;
}