Submission #1292059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292059		haha	Evacuation plan (IZhO18_plan)	C++20	22 / 100	194 ms	25304 KiB

plan

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

int n,m,k,q;
int npp[maxn],U[maxn],V[maxn],dsu[maxn];
ll dist[maxn];
int par[maxn],depth[maxn],sz[maxn],pos[maxn],arr[maxn],chainID[maxn],chainHead[maxn];
int curChain,curPos;
ll tree[4*maxn];
vector<pair<int,int>> g[maxn],mst[maxn];
struct edge{
    int u,v;
    ll w;
};
vector<edge> edges;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> Q;

void dijkstra()
{
    for(int i=1;i<=n;i++) dist[i]=1e18;
    for(int i=1;i<=k;i++){
        dist[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(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                Q.push({dist[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;
        par[v]=u;
        depth[v]=depth[u]+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)
{
    while(chainID[u]!=chainID[v]){
        if(chainID[u]>chainID[v]){
            u=par[chainHead[chainID[u]]];
        }
        else v=par[chainHead[chainID[v]]];
    }
    if(depth[u]<depth[v]) return u;
    return v;
}

void  build(int id,int l,int r)
{
    if(l==r){
        int v=arr[l];
        for(int i=0;i<mst[v].size();i++){
            int u=mst[v][i].f;
            ll w=mst[v][i].s;
            if(par[v]==u){
                tree[id]=w;
                break;
            }
        }
        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 1e18;
    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=1e18;
    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<=m;i++){
        int u=U[i];
        int v=V[i];
        edges.push_back({u,v,min(dist[u],dist[v])});
    }
    sort(edges.begin(),edges.end(),[](edge a,edge b){
         return a.w>b.w;
    });
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int i=0;i<edges.size();i++){
        int u=edges[i].u;
        int v=edges[i].v;
        ll w=edges[i].w;
        if(join(u,v)){
            mst[u].push_back({v,w});
            mst[v].push_back({u,w});
        }
    }
    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: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46