Submission #1291950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291950		haha	Evacuation plan (IZhO18_plan)	C++20	0 / 100	92 ms	16680 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];
int a[maxn],depth[maxn],sz[maxn],pos[maxn],arr[maxn],ChainID[maxn],ChainHead[maxn];
int CurChain,CurPos;
int tree[4*maxn];
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]=1e18;
    for(int i=1;i<=k;i++){
        dis[npp[i]]=0;
        Q.push({0,npp[i]});
    }
    while(!Q.empty()){
        int u=Q.top().s;
        Q.pop();
        for(int i=0;i<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)
{
    sz[u]=1;
    for(int i=0;i<mst[u].size();i++){
        int v=mst[u][i].f;
        if(v==p) continue;
        up[v][0]=u;
        depth[v]=depth[u]+1;
        par[v]=u;
        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<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<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);
    int k=depth[v]-depth[u];
    for(int j=0;(1<<j)<=k;j++){
        if(k>>j&1) v=up[v][j];
    }
    if(u==v) return u;
    k=__lg(depth[u]);
    for(int j=k;j>=0;j--){
        if(up[u][j]!=up[v][j]){
            u=up[u][j];
            v=up[v][j];
        }
    }
    return up[u][0];
}

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]);
}

int get(int id,int l,int r,int u,int v)
{
    if(r<u||v<l) return 1e9;
    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));
}

int query(int u,int v)
{
    int p=lca(u,v);
    int ans=1e9;
    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<=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;
    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;
    });
    int cnt=0;
    for(int i=0;i<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});
        }
    }
    for(int i=1;i<=n;i++) a[i]=dis[i];
    CurPos=CurChain=1;
    dfs(1,1);
    HLD(1,1);
    build(1,1,n);
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<query(u,v)<<'\n';
    }

}

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