Submission #1302799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302799		haha	Evacuation plan (IZhO18_plan)	C++20	22 / 100	414 ms	46500 KiB

plan

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

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

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

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

void dijkstra()
{
    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});
            }
        }
    }
}

void dfs(int u,int p)
{
    sz[u]=1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i].f;
        if(v==p) continue;
        depth[v]=depth[u]+1;
        par[v]=u;
        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<g[u].size();i++){
        int v=g[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<g[u].size();i++){
        int v=g[u][i].f;
        if(v!=p&&v!=nxt){
            curChain++;
            hld(v,u);
        }
    }
}

void build(int id,int l,int r)
{
    if(l==r){
        int u=arr[l];
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].f;
            ll w=g[u][i].s;
            if(par[u]==v){
                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));
}

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;
    else return v;
}

ll query(int u,int v)
{
    ll ans=1e18;
    int p=lca(u,v);
    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>>v>>w;
        U[i]=u;
        V[i]=v;
        W[i]=w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    cin>>k;
    for(int i=1;i<=n;i++) dis[i]=1e18;
    for(int i=1;i<=k;i++){
        int npp;
        cin>>npp;
        Q.push({0,npp});
        dis[npp]=0;
    }
    dijkstra();
    for(int i=1;i<=m;i++){
        edges.push_back({U[i],V[i],min(dis[U[i]],dis[V[i]])});
    }
    sort(edges.begin(),edges.end(),[](edge a,edge b){
         return a.w>b.w;
    });
    for(int i=1;i<=n;i++) g[i].clear();
    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(Union(u,v)){
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
    }
    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