제출 #1033442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033442		pera	Evacuation plan (IZhO18_plan)	C++17	0 / 100	786 ms	37280 KiB

plan

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n , m , k , q;
vector<int> d(N) , p(N) , ans(N) , S(N) , T(N);
vector<vector<int>> e(N) , g(N) , w(N);
int find(int u){
   return u == p[u] ? u : p[u] = find(p[u]);
}
void unite(int u , int v){
   u = find(u);
   v = find(v);
   p[v] = u;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin >> n >> m;
   for(int i = 1;i <= m;i ++){
      int u , v , x;
      cin >> u >> v >> x;
      g[u].push_back(v);
      w[u].push_back(x);
      g[v].push_back(u);
      w[v].push_back(x);
   }
   cin >> k;
   for(int i = 1;i <= n;i ++){
      d[i] = ans[i] = -1;
   }
   priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
   for(int i = 1;i <= k;i ++){
      int g;
      cin >> g;
      d[g] = 0;
      pq.push({d[g] , g});
   }
   int q;
   cin >> q;
   for(int i = 1;i <= q;i ++){
      cin >> S[i] >> T[i];
   }
   while(pq.size()){
      auto [s , u] = pq.top();
      pq.pop();
      if(d[u] != s){
         continue;
      }
      for(int x = 0;x < (int)g[u].size();x ++){
         if(d[g[u][x]] == -1 || d[g[u][x]] > s + w[u][x]){
            d[g[u][x]] = s + w[u][x];
            pq.push({d[g[u][x]] , g[u][x]});
         }
      }
   }
   for(int i = 1;i <= n;i ++){
      e[d[i]].push_back(i);
   }
   vector<vector<int>> query(n + 1);
   auto Reset = [&](){
      for(int i = 0;i <= n;i ++){
         vector<int>().swap(query[i]);
         p[i] = i;
      }
   };
   for(int bit = 18;bit >= 0;bit --){
      Reset();
      for(int i = 1;i <= q;i ++){
         if(ans[i] + (1 << bit) <= n){
            query[ans[i] + (1 << bit)].push_back(i);
         }
      }
      for(int x = n;x >= 0;x --){
         for(int u : e[x]){
            for(int v : g[u]){
               if(d[u] <= d[v]){
                  unite(u , v);
               }
            }
         }
         for(int id : query[x]){
            if(find(S[id]) == find(T[id])){
               ans[id] += (1 << bit);
            }
         }
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << ans[i] << " ";
   }
   cout << endl;
}

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