oj.uz

Submission #568249

# Submission time Handle Problem Language Result Execution time Memory
568249 2022-05-25T03:16:09 Z almothana05 Restore Array (RMI19_restore) C++14
7 / 100
 600 ms 64692 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62936 KB Output is correct
2 Correct 36 ms 62892 KB Output is correct
3 Correct 36 ms 62908 KB Output is correct
4 Correct 37 ms 62892 KB Output is correct
5 Correct 32 ms 62880 KB Output is correct
6 Correct 33 ms 62932 KB Output is correct
7 Correct 34 ms 62892 KB Output is correct
8 Correct 33 ms 62936 KB Output is correct
9 Correct 34 ms 62920 KB Output is correct
10 Correct 31 ms 62832 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 64512 KB Output is correct
2 Correct 564 ms 64676 KB Output is correct
3 Correct 559 ms 64656 KB Output is correct
4 Correct 561 ms 64692 KB Output is correct
5 Execution timed out 1082 ms 64588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 64512 KB Output is correct
2 Correct 564 ms 64676 KB Output is correct
3 Correct 559 ms 64656 KB Output is correct
4 Correct 561 ms 64692 KB Output is correct
5 Execution timed out 1082 ms 64588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62936 KB Output is correct
2 Correct 36 ms 62892 KB Output is correct
3 Correct 36 ms 62908 KB Output is correct
4 Correct 37 ms 62892 KB Output is correct
5 Correct 32 ms 62880 KB Output is correct
6 Correct 33 ms 62932 KB Output is correct
7 Correct 34 ms 62892 KB Output is correct
8 Correct 33 ms 62936 KB Output is correct
9 Correct 34 ms 62920 KB Output is correct
10 Correct 31 ms 62832 KB Output is correct
11 Correct 525 ms 64512 KB Output is correct
12 Correct 564 ms 64676 KB Output is correct
13 Correct 559 ms 64656 KB Output is correct
14 Correct 561 ms 64692 KB Output is correct
15 Execution timed out 1082 ms 64588 KB Time limit exceeded
16 Halted 0 ms 0 KB -