oj.uz

Submission #294997

# Submission time Handle Problem Language Result Execution time Memory
294997 2020-09-09T11:52:05 Z BThero Railway Trip (JOI17_railway_trip) C++17
5 / 100
 65 ms 384 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;
const int INF = (int)1e9;

int lvl[MAXN];
int dist[MAXN];
int n, k, q;

void solve() {
  scanf("%d %d %d", &n, &k, &q);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &lvl[i]);
  }
  
  for (int i = 1; i <= q; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    
    if (lvl[a] > lvl[b]) {
      swap(a, b);
    }
    
    fill(dist + 1, dist + n + 1, INF);
    priority_queue<pii> Q;
    dist[a] = 0;
    Q.push(mp(0, a));
    
    while (!Q.empty()) {
      int cd = -Q.top().fi;
      int v = Q.top().se;
      Q.pop();
      
      if (cd != dist[v]) {
        continue;
      }
      
      for (int to = v - 1, mx = -1, cnt = 0; to > 0; --to) {
        if (lvl[to] > mx) {
          mx = lvl[to];
          int w;
          
          if (lvl[to] >= lvl[v]) {
            w = cd + cnt + 1;
          }
          else {
            w = cd + 1;
          }
          
          if (w < dist[to]) {
            dist[to] = w;
            Q.push(mp(-dist[to], to));
          }
        }
        
        cnt += (lvl[to] >= lvl[v]);
      }
      
      for (int to = v + 1, mx = -1, cnt = 0; to <= n; ++to) {
        if (lvl[to] > mx) {
          mx = lvl[to];
          
          int w;
          
          if (lvl[to] >= lvl[v]) {
            w = cd + cnt + 1;
          }
          else {
            w = cd + 1;
          }
          
          if (w < dist[to]) {
            dist[to] = w;
            Q.push(mp(-dist[to], to));
          }
        }
        
        cnt += (lvl[to] >= lvl[v]);
      }
    }
    
    printf("%d\n", dist[b] - 1);
  }
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message

railway_trip.cpp: In function 'void solve()':
railway_trip.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d %d %d", &n, &k, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d", &lvl[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d %d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 288 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 384 KB Output is correct
2 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 384 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 384 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -