Submission #522305

#	Time	Username	Problem	Language	Result	Execution time	Memory
522305		inluminas	Evacuation plan (IZhO18_plan)	C++17	100 / 100	780 ms	54200 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

const int lmt=1e5+10;
vector<pair<int,int>>adj[lmt];
int dis[lmt],par[lmt],mn[lmt][20],P[lmt][20],lvl[lmt];

void dij(){
  for(int i=0;i<lmt;i++) dis[i]=INT_MAX;
  int k;
  cin>>k;
  set<pair<int,int>>q;
  while(k--){
    int x;
    cin>>x;
    dis[x]=0;
    q.insert({0,x});
  }
  while(!q.empty()){
    int 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[v]>dis[u]+w){
        dis[v]=dis[u]+w;
        q.insert({dis[v],v});
      }
    }
  }
}

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

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

int lca(int p,int q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(int i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=P[p][i];
    }
  }
  if(p==q) return p;
  for(int i=19;i>=0;i--){
    if(P[p][i]!=-1 && P[p][i]!=P[q][i]){
      p=P[p][i],q=P[q][i];
    }
  }
  return P[p][0];
}

int f(int u,int p){
  int res=INT_MAX;
  for(int i=19;i>=0;i--){
    if(lvl[u]-(1<<i)>=lvl[p]){
      res=min(res,mn[u][i]);
      u=P[u][i];
    }
  }
  return res;
}

int main(){
  fastio;

  int n,m;
  cin>>n>>m;
  vector<array<int,3>>e;
  for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    adj[u].push_back({w,v});
    adj[v].push_back({w,u});
    e.push_back({0,u,v});
  }
  dij();


  for(auto& x:e){
    x[0]=min(dis[x[1]],dis[x[2]]);
  }

  sort(e.begin(),e.end());
  reverse(e.begin(),e.end());

  for(int i=1;i<=n;i++){
    adj[i].clear();
    par[i]=i;
  }

  for(auto x:e){
    int u=findpar(x[1]),v=findpar(x[2]);
    if(u==v) continue;
    par[u]=v;
    adj[x[1]].push_back({x[0],x[2]});
    adj[x[2]].push_back({x[0],x[1]});
  }

  for(int i=1;i<=n;i++){
    for(int j=0;j<20;j++){
      P[i][j]=-1,mn[i][j]=INT_MAX;
    }
  }

  dfs(1,0);

  for(int j=1;j<20;j++){
    for(int 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];
      }
    }
  }

  int Q;
  cin>>Q;
  while(Q--){
    int u,v;
    cin>>u>>v;
    int p=lca(u,v);
    int res=min(f(u,p),f(v,p));
    cout<<res<<endl;
  }
  return 0;
}

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