oj.uz

Submission #568247

# Submission time Handle Problem Language Result Execution time Memory
568247 2022-05-25T03:15:11 Z almothana05 Restore Array (RMI19_restore) C++14
0 / 100
 499 ms 64724 KB 
#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 * 2 ; 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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 62924 KB Integer 10011111 violates the range [-1, 1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 499 ms 64724 KB Expected integer, but "111111111111111111111111111111...1111111111011111111111111111111" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 499 ms 64724 KB Expected integer, but "111111111111111111111111111111...1111111111011111111111111111111" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 62924 KB Integer 10011111 violates the range [-1, 1]
2 Halted 0 ms 0 KB -