Submission #169467

#	Time	Username	Problem	Language	Result	Execution time	Memory
169467		RafaelSus	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1301 ms	64216 KiB

plan

#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back

int n,m,par[N],sz[N],k,up[20][N];
ll mn[20][N],tin[N],tout[N],timer;
ll dist[N];
vector<pair<int,ll>>g[N];
vector<pair<int,int>>road;

int find(int a){
  if(a==par[a])return a;
  return par[a]=find(par[a]);
}

void merge(int a,int b){
  a=find(a);b=find(b);
  if(sz[a]<sz[b])swap(a,b);
  sz[a]+=sz[b];
  par[b]=a;
}

void dfs(int v,int p,ll w){
  up[0][v]=p;
  mn[0][v]=w;
  tin[v]=++timer;
  for(int i=1;i<=19;i++){
    up[i][v]=up[i-1][up[i-1][v]];
    mn[i][v]=min(mn[i-1][v],mn[i-1][up[i-1][v]]);
  }
  for(auto to:g[v])
    if(to.first!=p)dfs(to.first,v,to.second);
  tout[v]=++timer;
}

bool upper(int a,int b){
  return tin[a]<=tin[b]&&tout[a]>=tout[b];
}

ll get(int a,int b){
  ll res=inf;
  if(upper(a,b)){
    for(int i=19;i>=0;--i){
      if(!upper(up[i][b],a)){
        res=min(res,mn[i][b]);
        b=up[i][b];
      }
    }
    res=min(res,mn[0][b]);
  }else if(upper(b,a)){
    for(int i=19;i>=0;--i){
      if(!upper(up[i][a],b)){
        res=min(res,mn[i][a]);
        a=up[i][a];
      }
    }
    res=min(res,mn[0][b]);
  }else{
    for(int i=19;i>=0;--i){
      if(!upper(up[i][b],a)){
        res=min(res,mn[i][b]);
        b=up[i][b];
      }
    }
    res=min(res,mn[0][b]);
    for(int i=19;i>=0;--i){
      if(!upper(up[i][a],b)){
        res=min(res,mn[i][a]);
        a=up[i][a];
      }
    }
    res=min(res,mn[0][b]);
  }
  return res;
}

int main(){
  //ios::sync_with_stdio(false);
  //cin.tie(0); cout.tie(0);
  
  cin>>n>>m;
  for(int i=1;i<=n;i++){par[i]=i;sz[i]=1;}
  for(int i=0;i<m;i++){
    int a,b;ll c;
    cin>>a>>b>>c;
    g[a].pb({b,c});
    g[b].pb({a,c});
    road.pb({a,b});
  }  
  priority_queue<pair<ll,int>> q;
  cin>>k;
  for(int i=1;i<=n;i++)dist[i]=inf;
  for(int i=0;i<k;i++){
    int v;cin>>v;
    dist[v]=0;q.push({0,v});
  }
  while(!q.empty()){
    int v=q.top().second;
    q.pop();
    for(auto x:g[v]){
      if(dist[x.first]>dist[v]+x.second){
        dist[x.first]=dist[v]+x.second;
        q.push({-dist[x.first],x.first});
      }
    }
  }
  for(int i=1;i<=n;i++)g[i].clear();
  sort(road.begin(),road.end(),[&](pair<int,int>a,pair<int,int>b){
    ll fi=min(dist[a.first],dist[a.second]);
    ll se=min(dist[b.first],dist[b.second]);
    return fi>se;
  });
  for(int i=0;i<m;i++){
    int a=road[i].first,b=road[i].second;
    ll w=min(dist[a],dist[b]);
    if(find(a)!=find(b)){
      g[a].pb({b,w});
      g[b].pb({a,w});
      merge(a,b);
    }
  }
  dfs(1,1,inf);
  int Q;
  cin>>Q;
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    cout<<get(a,b)<<'\n';
  }
}

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