제출 #872534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872534		epicci23	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1039 ms	47284 KiB

plan

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

/*
 implement and debug smart
 DONT GET STUCK ON ONE APPROACH
 write smth on paper
 edge cases (n=1?)
 rewrite the problem
 simplify
 transform the problem into other problem
*/


struct DSU{
  vector<int> par;
  vector<int> siz;

  DSU(int n){
    par.resize(n+5);
    iota(all(par),0LL);
    siz.assign(n+5,1LL);
  }

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

  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    siz[b]+=siz[a];
    par[a]=b;
  }
};

const int N = 1e5 + 5;

vector<array<int,2>> v[N];

void solve(){

  int n,m;
  cin >> n >> m;

  for(int i=1;i<=m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    v[a].pb({b,c});
    v[b].pb({a,c});
  }

  vector<int> nodes;
  int k;
  cin >> k;
  for(int i=1;i<=k;i++){
    int a;
    cin >> a;
    nodes.pb(a);
  }

  int q;
  cin >> q;

  int l[q+5],r[q+5];
  array<int,2> ar[q+5];

  for(int i=1;i<=q;i++){
    int a,b;
    cin >> a >> b;
    ar[i]={a,b};
    l[i]=0;
    r[i]=(int)1e12;
  }

  int dist[n+5];
  fill(dist,dist+n+5,1e18);

  for(int x:nodes) dist[x]=0;

  priority_queue<array<int,2>> pq;

  for(int x:nodes) pq.push({0,x});

  while(!pq.empty()){
    int d = pq.top()[0] * -1;
    int c = pq.top()[1];
    pq.pop();
    if(dist[c] < d) continue;
    for(auto x : v[c]){
      int u=x[0],cost=x[1];
      if(d+cost<dist[u]){
        dist[u]=d+cost;
        pq.push({-dist[u],u});
      }
    }
  }

  vector<array<int,2>> dist_nodes;

  for(int i=1;i<=n;i++) dist_nodes.pb({dist[i],i});
    
  sort(all(dist_nodes));
  reverse(all(dist_nodes));

  for(int XD = 0 ; XD < 50 ; XD++){

    DSU dsu(n);
    vector<array<int,2>> check;
    for(int i=1;i<=q;i++) if(l[i]!=r[i]) check.pb({(r[i]+l[i]+1)/2,i});
    sort(all(check));
    reverse(all(check));

    int p=0;
    vector<int> vis(n+5,0);

    for(array<int,2> x : check){

      while(p<n && dist_nodes[p][0] >= x[0]){
        int cur = dist_nodes[p][1];
        vis[cur] = 1;
        for(auto edge : v[cur]) if(vis[edge[0]]) dsu.unite(edge[0],cur);
        p++;
      }

      int u = ar[x[1]][0];
      int w = ar[x[1]][1];

      if(dsu.find(u)==dsu.find(w)) l[x[1]] = x[0];
      else r[x[1]] = x[0] - 1;
    }  
  }

  for(int i=1;i<=q;i++){
    assert(l[i]==r[i]);
    cout << l[i] << endl;
  }

}

int32_t main(){

  cin.tie(0);
  ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();
}

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