Submission #568250

#	Time	Username	Problem	Language	Result	Execution time	Memory
568250		almothana05	Restore Array (RMI19_restore)	C++14	45 / 100	605 ms	64772 KiB

restore

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<pair<long long , long long> >gr[2000000];
long long dist[2000000] , vis[2000000];
priority_queue<pair<long long , long long> >q;
vector<vector<long long> >edge;
int main(){
   
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   long long menge , numm , nummer , que , cmp , bi;
   cin >> menge >> que;
   for(long long i = 0 ; i < menge;  i++){
      gr[i].push_back({i + 1 , 1});
      gr[i + 1].push_back({i , 0});

      edge.push_back({i , i + 1 , 1});
      edge.push_back({i + 1, i , 0});

   }
   while(que--){
      cin >> numm >> nummer >> cmp >> bi;
      // numm++;
      nummer++;
      if(bi == 0){
         cmp = nummer - numm - cmp;
         gr[numm].push_back({nummer , cmp});
         edge.push_back({numm , nummer , cmp});
      }
      else{
         cmp = nummer - numm - cmp + 1;
         cmp *= -1;
         gr[nummer].push_back({numm , cmp});
         edge.push_back({nummer , numm , cmp});
      }
   }
   for(long long i = 0 ; i < 2000000 ; i++){
      dist[i] = inf;
   }
   dist[0] = 0;
   for(long long k = 0 ; k < menge ; k++){
      for(long long i = 0 ; i < edge.size() ; i++){
         if(dist[edge[i][0]] != inf && dist[edge[i][0]] + edge[i][2] < dist[edge[i][1]]){
            dist[edge[i][1]] = dist[edge[i][0]] + edge[i][2];
         }
      }
   }
   for(long long i = 0 ; i < edge.size() ; i++){
      if(dist[edge[i][0]] != inf && dist[edge[i][0]] + edge[i][2] < dist[edge[i][1]]){
         cout << -1 << "\n";
         return 0;
      }
   }
   for(long long i = 0 ; i < menge ; i++){
      // cout << dist[i] << "\n";
      if(dist[i] == dist[i + 1]){
         cout << 0 << ' ';
      }
      else{
         cout << 1 << ' ';
      }
   }

}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:44:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(long long i = 0 ; i < edge.size() ; i++){
      |                             ~~^~~~~~~~~~~~~
restore.cpp:50:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(long long i = 0 ; i < edge.size() ; i++){
      |                          ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55