Submission #565819

#	Time	Username	Problem	Language	Result	Execution time	Memory
565819		almothana05	Evacuation plan (IZhO18_plan)	C++14	0 / 100	615 ms	68884 KiB

plan

#include<bits/stdc++.h>
#define mod 1000000007
//////////////////////////////////////////////////////////
#define inf 100000000000000000
using namespace std;
vector<pair<int , int > >gr[300000];
priority_queue<pair<int , int> >q;
vector<int>kinder[300000];
vector<vector<int> >mst;
int dis[300000] , f[300000] , fa[300000] , lift[300000][20];;
int menge , numm , nummer , que , ed , npp;
void bfs(){
   while(q.size()){
      int jet = q.top().second , cmp = -q.top().first;
      q.pop();
      for(int 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});
         }
      }
   }
}
int fater(int x){
   if(f[x] == x){
      return x;
   }
   f[x] = fater(f[x]);
   return f[x];
}
int pl;
void merge(int x , int y){
   // cout << x << ' ' << y << "\n";
   if(fater(x) != fater(y)){
      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(int x , int f){
   // cout << x << ' ' << f << "\n";
   lift[x][0] = f;
   for(int i = 1 ; i < 20 ; i++){
      lift[x][i] = lift[lift[x][i - 1]][i - 1];
   }
   for(int i = 0 ; i < kinder[x].size() ; i++){
      dfs(kinder[x][i] , x);
   }
}
int main(){
   // ios_base::sync_with_stdio(false);
   //  cin.tie(NULL);
   for(int i = 0 ; i < 300000 ; i++){
      dis[i] = mod;
      f[i] = i;
   }
   cin >> menge >> ed;
   pl = menge + 1;

   for(int 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(int i = 0 ; i < npp ; i++){
      cin >> numm;
      dis[numm] = 0;
      q.push({0 , numm});
   }
   bfs();
   for(int i = 1 ; i <= menge ; i++){
      cout << dis[i] << ' ';
   }
   cout << "\n";
   // cout << "\n";
   for(int i = 0 ; i < ed ; i++){
      mst[i][0] = min(dis[ mst[i][1] ]  ,dis[ mst[i][2] ] );
   }
   sort(mst.begin() , mst.end());
   for(int i = mst.size() -1 ; i >= 0 ; i--){
   // cout << mst[];
      merge(mst[i][1] , mst[i][2]);
   }
   pl--;
   dfs(pl , 0);
   for(int i = 1 ; i <= menge ; i++){
      for(int j = 0 ; j < 20 ; j++){
         cout << lift[i][j] << " " ;
      }
      cout << "\n";
   }
}

Compilation message (stderr)

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

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