Submission #1351307

#TimeUsernameProblemLanguageResultExecution timeMemory
1351307bunhadasouEvacuation plan (IZhO18_plan)C++20
100 / 100
552 ms36212 KiB
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define PB push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define bit(n,i) ((n>>i)&1)
#define TASK "cf"
using namespace std;


const int maxn=1e5+5;
const ll oo=1e18L+9;
ll d[maxn];
int dp[maxn],head[maxn],heavy[maxn],in[maxn],par[maxn],h[maxn];
int parrent[maxn],Rank[maxn];
bool check[maxn];
int n,m,k,q;
int time_dfs;
vector<pair<int,int>>adj[maxn];
vector<int>adj1[maxn];
pair<pair<int,int>,ll>edge[maxn*5];

void dfs(int u,int p){
    int mx=0;
    dp[u]=1;
    for (auto v:adj1[u]){
        if (v==p) continue;
        par[v]=u;
        h[v]=h[u]+1;
        dfs(v,u);
        dp[u]+=dp[v];
        if (dp[v]>mx) {
            mx=dp[v];
            heavy[u]=v;
        }
    }
}
void hld(int u,int res){
    in[u]=++time_dfs;
    head[u]=res;
    if (heavy[u]) hld(heavy[u],res);
    for (auto v:adj1[u]) if (v!=par[u]&&v!=heavy[u]) hld(v,v);
}

ll mini(ll a,ll b){
    if (a<b) return a; return b;
}

struct SEG{
    vector<ll>T;
    void init(int _n){
        T.assign(4*_n+5,oo);
    }
    void upd(int node,int l,int r,int u,int v,ll val){
        if (u>r||v<l) return;
        if (u<=l&&r<=v) {
            T[node]=val;
            return;
        }
        int mid=(l+r)>>1;
        upd(node<<1,l,mid,u,v,val);
        upd(node<<1|1,mid+1,r,u,v,val);
        T[node]=mini(T[node<<1],T[node<<1|1]);
    }
    ll get(int node,int l,int r,int u,int v){
        if (u>r||v<l) return oo;
        if (u<=l&&r<=v) return T[node];
        int mid=(l+r)>>1;
        return mini(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
    }
};

SEG T;

ll path(int u,int v){
    ll ans=oo;
    while(head[u]!=head[v]){
        if (h[head[u]]>h[head[v]]) swap(u,v);
        ans=mini(ans,T.get(1,1,n,in[head[v]],in[v]));
        v=par[head[v]];
    }
    if (in[u]>in[v]) swap(u,v);
    ans=mini(ans,T.get(1,1,n,in[u],in[v]));
    return ans;
}

void dijkstra(){
    priority_queue<pair<ll,int>>pq;
    for (int i=1;i<=n;i++) if (d[i]==0) pq.push(mp(0,i));
    while(!pq.empty()){
        int u=pq.top().se;
        pq.pop();
        if (check[u]) continue;
        check[u]=1;
        for (auto v:adj[u]){
            if (d[v.fi]>d[u]+v.se){
                d[v.fi]=d[u]+v.se;
                pq.push(mp(-d[v.fi],v.fi));
            }
        }
    }
}

int find(int u){
    if (u==parrent[u]) return u;
    return parrent[u]=find(parrent[u]);
}

bool UNION(int u,int v){
    u=find(u);v=find(v);
    if (u==v) return 0;
    if (Rank[u]<Rank[v]) swap(u,v);
    parrent[v]=u;
    Rank[u]+=Rank[v];
    return 1;
}

int main(){
    // freopen(TASK".inp","r",stdin);
    // freopen(TASK".out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int x,y,z ;cin>>x>>y>>z;
        edge[i]=mp(mp(x,y),z);
        adj[x].PB(mp(y,z));
        adj[y].PB(mp(x,z));
    }
    for (int i=1;i<=n;i++) d[i]=oo;
    cin>>k;
    for (int i=1;i<=k;i++) {
        int x; cin>>x;
        d[x]=0;
    }
    dijkstra();

    for (int i=1;i<=m;i++) edge[i].se=mini(d[edge[i].fi.fi],d[edge[i].fi.se]);
    sort(edge+1,edge+m+1,[&](auto u,auto v){
        return u.se>v.se;
    });
    for (int i=1;i<=n;i++) {
        Rank[i]=1;
        parrent[i]=i;
    }
    for (int i=1;i<=m;i++) {
        int u=edge[i].fi.fi,v=edge[i].fi.se;
        if (UNION(u,v)) {
            adj1[u].PB(v);
            adj1[v].PB(u);
        }
    }
    dfs(1,0);
    hld(1,1);
    T.init(n);
    for (int i=1;i<=n;i++) T.upd(1,1,n,in[i],in[i],d[i]);
    cin>>q;
    while(q--){
        int u,v; cin>>u>>v;
        cout<<path(u,v)<<"\n";

    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...