Submission #568253

#	Time	Username	Problem	Language	Result	Execution time	Memory
568253		almothana05	Restore Array (RMI19_restore)	C++14	100 / 100	376 ms	980 KiB

restore

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

      edge[0].push_back(i);
      edge[1].push_back(i + 1);
      edge[2].push_back(1);

      edge[0].push_back(i + 1);
      edge[1].push_back(i);
      edge[2].push_back(0);

   }
   while(que--){
      cin >> numm >> nummer >> cmp >> bi;
      // numm++;
      nummer++;
      if(bi == 0){
         cmp = nummer - numm - cmp;
         edge[0].push_back(numm);
         edge[1].push_back(nummer);
         edge[2].push_back(cmp);
      }
      else{
         cmp = nummer - numm - cmp + 1;
         cmp *= -1;
         edge[0].push_back(nummer);
         edge[1].push_back(numm);
         edge[2].push_back(cmp);
      }
   }
   for(int i = 0 ; i < 20000 ; i++){
      dist[i] = inf;
   }
   dist[0] = 0;
   for(int k = 0 ; k < menge ; k++){
      for(int i = 0 ; i < edge[1].size() ; i++){
         if(dist[edge[0][i]] != inf && dist[edge[0][i]] + edge[2][i] < dist[edge[1][i]]){
            dist[edge[1][i]] = dist[edge[0][i]] + edge[2][i];
         }
      }
   }
   for(int i = 0 ; i < edge[1].size() ; i++){
      if(dist[edge[0][i]] != inf && dist[edge[0][i]] + edge[2][i] < dist[edge[1][i]]){
         cout << -1 << "\n";
         return 0;
      }
   }
   for(int 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:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |       for(int i = 0 ; i < edge[1].size() ; i++){
      |                       ~~^~~~~~~~~~~~~~~~
restore.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i = 0 ; i < edge[1].size() ; i++){
      |                    ~~^~~~~~~~~~~~~~~~

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