Submission #1112656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112656		noyancanturk	Evacuation plan (IZhO18_plan)	C++17	100 / 100	682 ms	43960 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
using pii=pair<int,int>;
const int lim=1e5+100;

int parent[lim],sz[lim],tt[lim];
int find(int i){
  if(parent[i]==i)return i;
  return find(parent[i]);
}
int findtime(int i,int t){
  if(i==parent[i]||t<tt[i])return i;
  return findtime(parent[i],t);
}
void unite(int i,int j,int t){
  i=find(i),j=find(j);
  if(i^j){
    if(sz[i]<sz[j])swap(i,j);
    sz[i]+=sz[j];
    parent[j]=i;
    tt[j]=t;
  }
}

signed main(){
  int n,m;
  cin>>n>>m;
  vector<pii>v[n+1];
  while(m--){
    int x,y,w;
    cin>>x>>y>>w;
    v[x].pb({y,w});
    v[y].pb({x,w});
  }
  int dist[n+1];
  for(int i=1;i<=n;i++){
    dist[i]=INT_MAX;
  }
  priority_queue<pii,vector<pii>,greater<pii>>pq;
  cin>>m;
  while(m--){
    int x;
    cin>>x;
    pq.push({0,x});
    dist[x]=0;
  }
  while(pq.size()){
    auto[ds,node]=pq.top();
    pq.pop();
    if(ds!=dist[node])continue;
    for(auto[j,w]:v[node]){
      if(w+ds<dist[j]){
        dist[j]=w+ds;
        pq.push({dist[j],j});
      }
    }
  }
  for(int i=1;i<=n;i++){
    parent[i]=i;
    sz[i]=1;
    tt[i]=-1;
    dist[i]=-dist[i];
  }
  int p[n];
  iota(p,p+n,1);
  sort(p,p+n,[&](int i,int j)->bool {
    return dist[i]<dist[j];
  });
  for(int i:p){
    for(auto[j,w]:v[i]){
      if(dist[j]<=dist[i]){
        unite(i,j,dist[i]);
      }
    }
  }
  cin>>m;
  while(m--){
    int x,y;
    cin>>x>>y;
    int l=-INT_MAX,r=-1,ans=0;
    while(l<=r){
      int mid=l+r>>1;
      if(findtime(x,mid)==findtime(y,mid)){
        ans=mid;
        r=mid-1;
      }else{
        l=mid+1;
      }
    }
    cout<<-ans<<'\n';
  }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:84:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |       int mid=l+r>>1;
      |               ~^~

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