Submission #565855

#	Time	Username	Problem	Language	Result	Execution time	Memory
565855		almothana05	Evacuation plan (IZhO18_plan)	C++14	100 / 100	932 ms	118636 KiB

plan

#include<bits/stdc++.h>
#define mod 1000000007
//////////////////////////////////////////////////////////
#define inf 100000000000000000
using namespace std;
vector<pair<long long , long long > >gr[300000];
priority_queue<pair<long long , long long> >q;
vector<long long>kinder[300000] , pow2 , erg;
vector<vector<long long> >mst;
long long dis[300000] , f[300000] , fa[300000] , lift[300000][20] ,  level[300000];;
long long menge , numm , nummer , que , ed , npp , cmp;
void bfs(){
   while(q.size()){
      long long jet = q.top().second , cmp = -q.top().first;
      q.pop();
      for(long long i = 0 ; i < gr[jet].size() ; i++){
         if(cmp + gr[jet][i].second < dis[gr[jet][i].first]){
            dis[gr[jet][i].first] = cmp + gr[jet][i].second;
            q.push({-dis[gr[jet][i].first] , gr[jet][i].first});
         }
      }
   }
}
long long fater(long long x){
   if(f[x] == x){
      return x;
   }
   f[x] = fater(f[x]);
   return f[x];
}
long long pl;
void merge(long long x , long long y , int z){
   // cout << x << ' ' << y << "\n";
   if(fater(x) != fater(y)){
      erg.push_back(z);
      fa[fater(x)] = pl;
      fa[fater(y)] = pl;
      kinder[pl].push_back(fater(x));
      kinder[pl].push_back(fater(y));
      f[fater(x)] = pl;
      f[fater(y)] = pl;
      pl++;
   }
}

void dfs(long long x , long long f){
   // cout << x << ' ' <<  f << "\n";
   level[x] = level[f] + 1;
   if(f == 0){
      level[x] = 0;
   }
   lift[x][0] = f;
   for(long long i = 1 ; i < 20 ; i++){
      lift[x][i] = lift[lift[x][i - 1]][i - 1];
   }
   for(long long i = 0 ; i < kinder[x].size() ; i++){
      dfs(kinder[x][i] , x);
   }
}
long long jump(long long x , long long mal){
   for(long long i = 19 ; i >= 0 ; i--){
      if(pow2[i] <= mal){
         x = lift[x][i];
         mal -= pow2[i];
      }
   }
   return x;
}
long long lca(long long x , long long y){
   if(level[x] > level[y]){
      swap(x , y);
   }
   y = jump(y , level[y] - level[x]);
   if(y == x){
      return y;
   }
   for(long long i = 19 ; i >= 0 ; i--){
      if(lift[x][i] != lift[y][i]){
         x = lift[x][i];
         y = lift[y][i];
      }
   }
   return lift[x][0];
}
int main(){
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   for(long long i = 0 ; i < 300000 ; i++){
      dis[i] = mod;
      f[i] = i;
   }
   pow2.push_back(1);
   for(long long i = 1 ; i < 20 ; i++){
      pow2.push_back(2 * pow2[i - 1]);
   }
   cin >> menge >> ed;
   pl = menge + 1;

   for(long long i = 0 ; i < ed ; i++){
      cin >> numm >> nummer >> que ;
      mst.push_back({0 , nummer , numm});
      gr[numm].push_back({nummer , que});
      gr[nummer].push_back({numm , que});
   }
   cin >> npp;
   for(long long i = 0 ; i < npp ; i++){
      cin >> numm;
      dis[numm] = 0;
      q.push({0 , numm});
   }
   bfs();
   // for(long long i = 1 ; i <= menge ; i++){
   //    cout << dis[i] << ' ';
   // }
   // cout << "\n";
   // cout << "\n";
   for(long long i = 0 ; i < ed ; i++){
      mst[i][0] = min(dis[ mst[i][1] ]  ,dis[ mst[i][2] ] );
   }
   sort(mst.begin() , mst.end());
   for(long long i = mst.size() -1 ; i >= 0 ; i--){
   // cout << mst[];
      merge(mst[i][1] , mst[i][2] , mst[i][0]);
   }
   pl--;
   level[pl] = 0;
   // cout << "\n\n\n\n\n";
   dfs(pl , 0);
   // for(long long i = 1 ; i <= menge ; i++){
   //    for(long long j = 0 ; j < 20 ; j++){
   //       cout << lift[i][j] << " " ;
   //    }
   //    cout << "\n";
   // }
   cin >> que;
   while(que--){
      
      cin >> numm >> nummer;
      cmp = lca(numm , nummer);
      // cout << cmp << "    ";
      cmp -= menge;
      cout << erg[cmp - 1] << "\n";
   }
}

Compilation message (stderr)

plan.cpp: In function 'void bfs()':
plan.cpp:16:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |       for(long long i = 0 ; i < gr[jet].size() ; i++){
      |                             ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'void dfs(long long int, long long int)':
plan.cpp:56:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(long long i = 0 ; i < kinder[x].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~~~~

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