RiceFruit @ 2023-02-26 19:33:41
提交记录
出现了奇怪的 RE
报错信息:
Runtime Error.
Received signal 6: Aborted / IOT trap.
有无人能帮忙看一下?
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lid (id<<1)
#define rid (id<<1|1)
const int N=5e5+500,M=4e6+4000;
inline int read();
int n,m,p,C;
int dy[N];
int dis[M];
bool vis[M];
deque<int>q;
struct node{
int v;
int w;
};
vector<node>son[M];
void build1(int id,int l,int r){
if(l==r)
return;
int mid=l+r>>1;
build1(lid,l,mid);
build1(rid,mid+1,r);
son[id].push_back(node{lid,0});
son[id].push_back(node{rid,0});
return;
}
void build2(int id,int l,int r){
son[id].push_back(node{id+C,0});
if(l==r){
dy[l]=id+C;
return;
}
int mid=l+r>>1;
build2(lid,l,mid);
build2(rid,mid+1,r);
son[lid+C].push_back(node{id+C,0});
son[rid+C].push_back(node{id+C,0});
return;
}
void add1(int id,int L,int R,int l,int r,int k){
if(L>=l&&R<=r){
son[k].push_back(node{id,1});
son[id+C].push_back(node{k+1,1});
return;
}
int mid=L+R>>1;
if(mid>=l)add1(lid,L,mid,l,r,k);
if(mid<r)add1(rid,mid+1,R,l,r,k);
return;
}
void add2(int id,int L,int R,int l,int r,int k){
if(L>=l&&R<=r){
son[k+1].push_back(node{id,1});
son[id+C].push_back(node{k,1});
return;
}
int mid=L+R>>1;
if(mid>=l)add2(lid,L,mid,l,r,k);
if(mid<r)add2(rid,mid+1,R,l,r,k);
}
void bfs(int s){
memset(dis,0x3f3f3f3f,sizeof dis);
q.push_front(s);
dis[s]=0;
while(q.size()){
int u=q.front();
q.pop_front();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<son[u].size();i++){
int v=son[u][i].v,w=son[u][i].w;
if(!vis[v]){
dis[v]=dis[u]+w;
if(w==0)
q.push_front(v);
else
q.push_back(v);
}
}
}
return;
}
signed main(){
n=read(),m=read(),p=read();
C=n<<2;
build1(1,1,n),build2(1,1,n);
for(int i=1;i<=m;i++){
int a=read(),b=read(),c=read(),d=read();
int s=(n<<3)+(i<<1);
add1(1,1,n,a,b,s),add2(1,1,n,c,d,s);
}
bfs(dy[p]);
for(int i=1;i<=n;i++)
printf("%lld\n",dis[dy[i]]/2);
return 0;
}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
by PikachuQAQ @ 2023-02-26 20:04:04
这边bdfs搜到的是评测机炸了
by PikachuQAQ @ 2023-02-26 20:04:35
@yaoyanfeng
by RiceFruit @ 2023-02-26 20:12:10
@Accept__ 已经解决了,是数组开小了