Submission #294997

#	Time	Username	Problem	Language	Result	Execution time	Memory
294997		BThero	Railway Trip (JOI17_railway_trip)	C++17	5 / 100	65 ms	384 KiB

railway_trip

// 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 (stderr)

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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55