Submission #1291951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291951		haha	Evacuation plan (IZhO18_plan)	C++20	0 / 100	96 ms	16700 KiB

plan

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int MOD=1e9+7;

int n,m,q,k;
vector<pair<int,int>> g[maxn],mst[maxn];
int U[maxn],V[maxn],npp[maxn],par[maxn],up[maxn][20],dsu[maxn];
ll a[maxn];                // changed to ll
int depth[maxn],sz[maxn],pos[maxn],arr[maxn],ChainID[maxn],ChainHead[maxn];
int CurChain,CurPos;
ll tree[4*maxn];           // changed to ll
ll dis[maxn];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> Q;
struct edge{
    int u,v;
    ll w;
};
vector<edge> adj;

void dijkstra()
{
    for(int i=1;i<=n;i++) dis[i]= (ll)4e18;
    while(!Q.empty()) Q.pop();
    for(int i=1;i<=k;i++){
        dis[npp[i]]=0;
        Q.push({0,npp[i]});
    }
    while(!Q.empty()){
        auto cur = Q.top(); Q.pop();
        ll d = cur.first; int u = cur.second;
        if(d != dis[u]) continue; // ignore outdated entries
        for(int i=0;i<(int)g[u].size();i++){
            int v=g[u][i].f;
            int w=g[u][i].s;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                Q.push({dis[v],v});
            }
        }
    }
}

int Find(int u)
{
    if(u==dsu[u]) return u;
    int p=Find(dsu[u]);
    dsu[u]=p;
    return p;
}

bool join(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return false;
    dsu[u]=v;
    return true;
}

void dfs(int u,int p)
{
    par[u]=p;               // set parent for queries
    sz[u]=1;
    for(int i=0;i<(int)mst[u].size();i++){
        int v=mst[u][i].f;
        if(v==p) continue;
        up[v][0]=u;
        depth[v]=depth[u]+1;
        for(int j=1;j<20;j++){
            up[v][j]=up[up[v][j-1]][j-1];
        }
        dfs(v,u);
        sz[u]+=sz[v];
    }
}

void HLD(int u,int p)
{
    if(!ChainHead[CurChain]) ChainHead[CurChain]=u;
    ChainID[u]=CurChain;
    pos[u]=CurPos;
    arr[CurPos]=u;
    CurPos++;
    int nxt=0;
    for(int i=0;i<(int)mst[u].size();i++){
        int v=mst[u][i].f;
        if(v==p) continue;
        if(nxt==0||sz[v]>sz[nxt]) nxt=v;
    }
    if(nxt) HLD(nxt,u);
    for(int i=0;i<(int)mst[u].size();i++){
        int v=mst[u][i].f;
        if(v!=p&&v!=nxt){
            CurChain++;
            HLD(v,u);
        }
    }
}

int lca(int u,int v)
{
    if(depth[u] < depth[v]) swap(u,v); // ensure u is deeper
    int diff = depth[u]-depth[v];
    for(int j=0;(1<<j)<=diff;j++){
        if((diff>>j)&1) u = up[u][j];
    }
    if(u==v) return u;
    for(int j=19;j>=0;j--){
        if(up[u][j]!=up[v][j]){
            u=up[u][j];
            v=up[v][j];
        }
    }
    return par[u];
}

void build(int id,int l,int r)
{
    if(l==r){
        int u=arr[l];
        tree[id]=a[u];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}

ll get(int id,int l,int r,int u,int v)
{
    if(r<u||v<l) return (ll)4e18;
    if(u<=l&&r<=v) return tree[id];
    int mid=(l+r)/2;
    return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

ll query(int u,int v)
{
    int p=lca(u,v);
    ll ans=(ll)4e18;
    while(ChainID[u]!=ChainID[p]){
        ans=min(ans,get(1,1,n,pos[ChainHead[ChainID[u]]],pos[u]));
        u=par[ChainHead[ChainID[u]]];
    }
    while(ChainID[v]!=ChainID[p]){
        ans=min(ans,get(1,1,n,pos[ChainHead[ChainID[v]]],pos[v]));
        v=par[ChainHead[ChainID[v]]];
    }
    if(depth[u]<depth[v]) ans=min(ans,get(1,1,n,pos[u]+1,pos[v]));
    else ans=min(ans,get(1,1,n,pos[v]+1,pos[u]));
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){ g[i].clear(); mst[i].clear(); }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>U[i]>>V[i]>>w;
        u=U[i];
        v=V[i];
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    cin>>k;
    for(int i=1;i<=k;i++) cin>>npp[i];
    dijkstra();

    for(int i=1;i<=n;i++) dsu[i]=i;
    adj.clear();
    for(int i=1;i<=m;i++){
        int u=U[i];
        int v=V[i];
        adj.push_back({u,v,min(dis[u],dis[v])});
    }
    sort(adj.begin(),adj.end(),[](edge A, edge B){
         return A.w>B.w;
    });
    for(int i=0;i<(int)adj.size();i++){
        int u=adj[i].u;
        int v=adj[i].v;
        if(join(u,v)){
            mst[u].push_back({v,adj[i].w});
            mst[v].push_back({u,adj[i].w}); // <-- fix: push both directions
        }
    }
    for(int i=1;i<=n;i++) a[i]=dis[i];

    // init up/par/ChainHead etc.
    for(int i=1;i<=n;i++){
        par[i]=0;
        depth[i]=0;
        sz[i]=0;
        for(int j=0;j<20;j++) up[i][j]=0;
        ChainHead[i]=0;
        pos[i]=0;
    }
    CurPos=1; CurChain=1;

    // run dfs/HLD for each component (in case forest)
    for(int i=1;i<=n;i++){
        if(par[i]==0){
            dfs(i,0);
            HLD(i,0);
            CurChain++;
        }
    }

    build(1,1,n);

    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        ll ans = query(u,v);
        if(ans >= (ll)4e18) cout << -1 << '\n'; // or some sentinel if unreachable
        else cout<<ans<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46