Submission #1033455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033455		pera	Evacuation plan (IZhO18_plan)	C++17	100 / 100	649 ms	35156 KiB

plan

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n , m , k , q , d[N] , p[N] , ans[N] , S[N] , T[N];
vector<int> order , 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;
      order.push_back(i);
   }
   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]});
         }
      }
   }
   sort(order.begin() , order.end() , [&](int x , int y){
      return d[x] < d[y];
   });
   reverse(order.begin() , order.end());
   vector<vector<int>> query(n + 1);
   auto Reset = [&](){
      for(int i = 0;i <= n;i ++){
         p[i] = i;
      }
   };
   for(int bit = 30;bit >= 0;bit --){
      Reset();
      vector<int> e;
      for(int i = 1;i <= q;i ++){
         ans[i] += (1 << bit);
         e.push_back(i);
      }
      sort(e.begin() , e.end() , [&](int x , int y){
         return ans[x] < ans[y];
      });
      int o = 0;
      for(int x = q - 1;x >= 0;x --){
         while(o < n && d[order[o]] >= ans[e[x]]){
            for(int v : g[order[o]]){
               if(d[order[o]] <= d[v]){
                  unite(v , order[o]);
               }
            }
            ++o;
         }
         ans[e[x]] -= (find(S[e[x]]) != find(T[e[x]])) * (1 << bit);
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << ans[i] << endl;
   }
}

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