求卡常或指出复杂度错误的地方
查看原帖
求卡常或指出复杂度错误的地方
555065
ChrysanthBlossom楼主2024/8/16 22:52

我知道裸的二维线段树优化建图过不了这题,但是好歹拿个 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;
}
2024/8/16 22:52
加载中...