Submission #522121

#	Time	Username	Problem	Language	Result	Execution time	Memory
522121		inluminas	Evacuation plan (IZhO18_plan)	C++17	0 / 100	829 ms	113452 KiB

plan

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

struct id{
  ll val=0,u=0,v=0;
};

const ll lmt=5e5+10;
ll dis[lmt],par[lmt],mn[lmt][30],P[lmt][30],lvl[lmt];
vector<pair<ll,ll>>adj[lmt];

void dijkstra(ll k){
  set<pair<ll,ll>>q;
  for(ll i=1;i<=k;i++){
    ll x;
    cin>>x;
    dis[x]=0;
    q.insert({0,x});
  }
  while(!q.empty()){
    ll val=(*q.begin()).first,u=(*q.begin()).second;
    q.erase(q.begin());

    if(val!=dis[u]){
      continue;
    }

    for(auto [w,v]:adj[u]){
      if(dis[u]+w<dis[v]){
        dis[v]=dis[u]+w;
        q.insert({dis[v],v});
      }
    }
  }
  return;
}

ll findpar(ll u){
  if(par[u]==u) return u;
  return par[u]=findpar(par[u]);
}

void dfs(ll u,ll p){
  for(auto [w,v]:adj[u]){
    if(v==p) continue;
    lvl[v]=lvl[u]+1;
    mn[v][0]=w,P[v][0]=u;
    dfs(v,u);
  }
}

ll lca(ll p,ll q){
  if(lvl[p]<lvl[q]) swap(p,q);
  ll pmn=inf,qmn=inf;
  for(ll i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q] && P[p][i]!=-1){
      pmn=min(pmn,mn[p][i]);
      p=P[p][i];
    }
  }
  if(p==q) return min(pmn,qmn);
  for(ll i=19;i>=0;i--){
    if(P[p][i]!=-1 && P[p][i]!=P[q][i]){
      pmn=min(pmn,mn[p][i]),qmn=min(qmn,mn[q][i]);
      p=P[p][i],q=P[q][i];
    }
  }

  pmn=min(pmn,mn[p][0]),qmn=min(qmn,mn[q][0]);
  return min(pmn,qmn);
}

int main(){
  fastio;


  ll n,m;
  cin>>n>>m;
  vector<id>e;
  for(ll i=1;i<=m;i++){
    ll u,v,w;
    cin>>u>>v>>w;
    e.push_back({1,u,v});
    adj[u].push_back({w,v});
    adj[v].push_back({w,u});
  }
  ll k;
  cin>>k;
  for(ll i=1;i<=n;i++){
    dis[i]=inf;
  }
  dijkstra(k);
  for(auto& x:e){
    x.val=min(dis[x.u],dis[x.v]);
  }
  sort(e.begin(),e.end(),[](id x,id y){
    return x.val>=y.val;
  });
  for(ll i=1;i<=n;i++){
    par[i]=i;
    adj[i].clear();
  }

  for(auto x:e){
    ll u=findpar(x.u), v=findpar(x.v);
    if(u==v) continue;
    par[u]=v;
    adj[x.u].push_back({x.val,x.v});
    adj[x.v].push_back({x.val,x.u});
  }

  for(ll i=0;i<=n;i++){
    for(ll j=0;j<30;j++){
      P[i][j]=-1,mn[i][j]=inf;
    }
  }

  dfs(1,0);

  for(ll j=1;j<30;j++){
    for(ll i=1;i<=n;i++){
      if(P[i][j-1]!=-1){
        mn[i][j]=min(mn[i][j-1],mn[P[i][j-1]][j-1]);
        P[i][j]=P[P[i][j-1]][j-1];
      }
    }
  }

  ll q;
  cin>>q;
  while(q--){
    ll u,v;
    cin>>u>>v;
    cout<<lca(u,v)<<endl;
  }
  return 0;
}

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