RT.为何爆500MB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define in inline
#define re register
#define pii pair<int,int>
#define se second
#define D(i,a,b) for(re int i = a;i >= b;i--)
#define F(i,a,b) for(re int i = a;i <= b;i++)
const int N = 5e4+10;
const int inf = 1e9;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}

int n,m,s,K;
struct made{
    int ver,nx,ed;
}e[3000010];
int hd[2000010],tot;
void add(int x,int y,int z){
//    cout<<x<<' '<<y<<' '<<z<<endl;
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}


int a[N];
void build(int p,int l,int r){
    if(l == r)return a[l] = p,void();
    add(p<<1,p,0),add(p<<1|1,p,0);
    add(p + K,(p<<1) + K,0),add(p + K,(p<<1|1) + K,0);
    int mid = l + r >> 1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void modify(int p,int x,int L,int R,int l,int r,int z,bool op){
    if(L <= l && r <= R)return op ? add(p,x,z) : add(x,p + K,z);
    int mid = l + r >> 1;
    if(L <= mid)modify(p<<1,x,L,R,l,mid,z,op);
    if(R > mid)modify(p<<1|1,x,L,R,mid+1,r,z,op);
}

void prin(int a[],int n){
    F(i,1,n)cout<<a[i]<<' ';
    cout<<endl;
}


int dfn[N],fa[N],dep[N],top[N];
int son[N],size[N];//尽量不用size -> siz 
struct Tree{
    made te[N<<1];
    int h[N],tot = 0,cnt = 0; 
    
    void tdd(int x,int y,int z){
        tot++;
        te[tot].nx = h[x],te[tot].ver = y,te[tot].ed = z,h[x] = tot;
    }
    void dfs1(int x){
        size[x] = 1;
        for(int i = h[x];i;i = te[i].nx){
            int y = te[i].ver;
            if(dep[y])continue;
            dep[y] = dep[x] + 1,fa[y] = x;
            dfs1(y);
            size[x] += size[y];
            if(!son[x] || size[y] > size[son[x]])son[x] = y;
        }
    }
    void dfs2(int x,int t){
        dfn[x] = ++cnt,top[x] = t;
        if(!son[x])return;
        dfs2(son[x],t);
        for(int i = h[x];i;i = te[i].nx){
            int y = te[i].ver;
            if(y != son[x] && y != fa[x])dfs2(y,y);
        }
    }
    void dfs(int x){
        if(x != top[x]){
            add(a[dfn[x]] + 2*K,a[dfn[fa[x]]] + 2*K,0),add(a[dfn[fa[x]]] + 3*K,a[dfn[x]] + 3*K,0);
        }
        add(a[dfn[x]] + 2*K,a[dfn[x]] + K,0),add(a[dfn[x]],a[dfn[x]] + 3*K,0);
        for(int i = h[x];i;i = te[i].nx){
            int y = te[i].ver,z = te[i].ed;
            if(y == fa[x])continue;
            dfs(y);
            add(a[dfn[x]],a[dfn[y]] + K,z),add(a[dfn[y]],a[dfn[x]] + K,z);
        }
    }//连树边 
    void caladd(int now,int x,int y,int z,bool op){
        while(top[x] != top[y]){
            if(dep[top[x]] < dep[top[y]])swap(x,y);
            op ? add(a[dfn[x]] + 3*K,now,z) : add(now,a[dfn[x]] + 2*K,z);//前后缀优化 
            x = fa[top[x]];
        }
        if(dep[x] > dep[y])swap(x,y);
        modify(1,now,dfn[x],dfn[y],1,n,z,op);//线段树优化 
    }//树上区间建边 
    void build(){dep[1] = 1,dfs1(1),dfs2(1,1);dfs(1);} 
}T; 


int sum;
struct Q{
    int u1,v1,u2,v2,z;
}q[1000010];
struct DSU{
    int fa[N];
    in void clear(){F(i,1,n)fa[i] = i;}
    int find(int x){
        if(fa[x] == x)return x;
        return fa[x] = find(fa[x]);
    }
    in void merge(int x,int y){
        x = find(x),y = find(y);
        fa[x] = y;
    }
    in bool lian(int x,int y){return find(x) == find(y);}
}U;//dsu


int cnt,d[2000010];
bool v[2000010];
void dij(int u){
    memset(d,0x3f,sizeof d);
    memset(v,0,sizeof v);
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push(make_pair(0,u)),d[u] = 0;
    while(!q.empty()){
        int x = q.top().se;q.pop();
        if(v[x])continue;
        v[x] = 1;
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver,z = e[i].ed;
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push(make_pair(d[y],y));
            }
        }
    }
}//dijdij
void work(){
    build(1,1,n);
    F(i,1,n)add(a[i] + K,a[i],0);
    T.build();cnt = 4 * K;
    F(i,1,sum){
        cnt++;
        T.caladd(cnt,q[i].u1,q[i].v1,q[i].z,1);
        T.caladd(cnt,q[i].u2,q[i].v2,0,0);
    }
    dij(a[dfn[s]]);
    F(i,1,n)printf("%d ",d[a[dfn[i]]] == d[0] ? -1 : d[a[dfn[i]]]);
    printf("\n");
}


int main(){
    n = read(),m = read(),s = read();
    K = 4 * n;
    U.clear();
    F(i,1,m){
        int op = read(),u1 = read(),v1 = read(),u2,v2,z;
        if(op == 1){
            u2 = read(),v2 = read();z = read();
            if(U.lian(u1,v1) && U.lian(u2,v2))q[++sum] = {u1,v1,u2,v2,z};
        }
        else{
            z = read();
            if(!U.lian(u1,v1))T.tdd(u1,v1,z),T.tdd(v1,u1,z),U.merge(u1,v1);
        }
    }
    work();
    
    return 0;
    
}