MLE on #35 68pts求调

rt，使用线段树优化建图+vector存图+01 bfs最短路，MLE on #35，求助

空间使用：约4 \times10^6 个vector<pair<int,bool> >+约4 \times10^6 个int+约4 \times10^6 大小的bitset+1个list(deque也试过了，没有用)。

自认为马蜂海星的code：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pc(x) putchar(x)

template<typename T> inline void fr(T& num){
    num=0;short sign=1;char ch=std::getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')sign=-1;
        ch=std::getchar();
    }
    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
    num=num*sign;
}
template<typename T>inline void fw(T x){
    if(x<0)std::putchar('-'),x=-x;
    if(x>9)fw(x/10);
    std::putchar(x%10+'0');
}

const int N=1<<19,M=N<<2;
vector<pair<int,bool> > g[N<<3];
int n,m,p;
int dis[N<<3];
bitset<N<<3> vis;

inline void bfs(int s){
    list<int> dq;
    memset(dis,0x3f,sizeof dis);
    dis[s]=0,dq.emplace_back(s);
    while(dq.size()){
        int x=dq.front();dq.pop_front();
        if(vis[x])continue;
        vis[x]=1;
        for(auto [y,z]:g[x]){
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                if(z)dq.emplace_back(y);
                else dq.emplace_front(y);
            }
        }
    }
}

namespace seg{
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
    inline void build(int p,int l,int r){
        if(l==r){
            g[p].emplace_back(p+M,0);
            g[p+M].emplace_back(p,0);
            return;
        }
        g[p].emplace_back(ls(p),0);
        g[p].emplace_back(rs(p),0);
        g[ls(p)+M].emplace_back(p+M,0);
        g[rs(p)+M].emplace_back(p+M,0);
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
    }
    inline void adde(int p,int from,int l,int r,int _l,int _r){
        if(l<=_l&&_r<=r)return g[from].emplace_back(p,1),void();
        int mid=(_l+_r)>>1;
        if(l<=mid)adde(ls(p),from,l,r,_l,mid);
        if(r>mid) adde(rs(p),from,l,r,mid+1,_r);
    }
    inline void add(int p,int l,int r,int L,int R,int _l,int _r){
        if(l<=_l&&_r<=r)return adde(1,p+M,L,R,1,n);
        int mid=(_l+_r)>>1;
        if(l<=mid)add(ls(p),l,r,L,R,_l,mid);
        if(r>mid)add(rs(p),l,r,L,R,mid+1,_r);
    }
    inline void query(int p,int pos,int _l,int _r){
        if(_l==_r)return bfs(p+M);
        int mid=(_l+_r)>>1;
        if(pos<=mid)query(ls(p),pos,_l,mid);
        else query(rs(p),pos,mid+1,_r);
    }
    inline void out(int p,int _l,int _r){
        if(_l==_r)return fw(dis[p]),pc('\n'),void();
        int mid=(_l+_r)>>1;
        out(ls(p),_l,mid);
        out(rs(p),mid+1,_r);
    }
}

void solve(){
    fr(n),fr(m),fr(p);
    seg::build(1,1,n);
    for(int i=1;i<=m;i++){
        int a,b,c,d;fr(a),fr(b),fr(c),fr(d);
        seg::add(1,a,b,c,d,1,n);
        seg::add(1,c,d,a,b,1,n);
    }
    seg::query(1,p,1,n);
    seg::out(1,1,n);
}
int main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0);cout.tie(0);
    int Count=1;//fr(Count);
    while(Count--)solve();
}
/*
多测不清空，OI见祖宗。
multitesting without clearing,oier meets the LCA.
十年OI一场空，不开LL见祖宗。
Ten years of OI just AFO,no #define int long long sees the LCA.
似是神犇成才处，实为蒟蒻黄泉路。
It is likely to be the Au medal for the big old,but in fact it is the Si medal for me.
黄题有恨无正解，码力不若小学生。
A yellow problem I can't AC,codeforces is not as NB as EUlar Shai.
今生无奈入OI，来世不做信竞人。
This life I am a Silly Being in oi,next life I won't f**k the sh*t of infomatics.
*/