oj.uz

Submission #913995

# Submission time Handle Problem Language Result Execution time Memory
913995 2024-01-20T17:44:39 Z cig32 Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
}
void solve(int tc) { 
  int n, k, m;
  cin >> n >> k >> m;
  int dist[n+1][n+1];
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=n; j++) {
      dist[i][j] = (i == j ? 0 : 1e9);
    }
  }
  for(int i=1; i<=m; i++) {
    int a, b;
    cin >> a >> b;
    if(a < b) {
      for(int j=a; j<a+k; j++) {
        for(int l=j+1; l<=b; l++) {
          dist[j][l] = 1;
        }
      }
    }
    else {
      for(int j=a; j>a-k; j--) {
        for(int l=j-1; l>=b; l--) {
          dist[j][l] = 1;
        }
      }
    }
  }
  for(int l=1; l<=n; l++) {
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][l]+dist[l][j]);
      }
    }
  }
  int q;
  cin >> q;
  while(q--) {
    int s, t;
    cin >> s >> t;
    cout << (dist[s][t] >= 1e7 ? -1 : dist[s][t]) << '\n';
  }
}

void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ brute.cpp -std=c++17 -O2 -o brute
./brute < input.txt
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 22 ms 2652 KB Output is correct
3 Correct 22 ms 1116 KB Output is correct
4 Correct 23 ms 2396 KB Output is correct
5 Correct 22 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 22 ms 2908 KB Output is correct
8 Correct 24 ms 1112 KB Output is correct
9 Correct 23 ms 2392 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 22 ms 1112 KB Output is correct
12 Correct 22 ms 1116 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 22 ms 2652 KB Output is correct
3 Correct 22 ms 1116 KB Output is correct
4 Correct 23 ms 2396 KB Output is correct
5 Correct 22 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 22 ms 2908 KB Output is correct
8 Correct 24 ms 1112 KB Output is correct
9 Correct 23 ms 2392 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 22 ms 1112 KB Output is correct
12 Correct 22 ms 1116 KB Output is correct
13 Execution timed out 2102 ms 32092 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 130 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 22 ms 2652 KB Output is correct
3 Correct 22 ms 1116 KB Output is correct
4 Correct 23 ms 2396 KB Output is correct
5 Correct 22 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 22 ms 2908 KB Output is correct
8 Correct 24 ms 1112 KB Output is correct
9 Correct 23 ms 2392 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 22 ms 1112 KB Output is correct
12 Correct 22 ms 1116 KB Output is correct
13 Execution timed out 2102 ms 32092 KB Time limit exceeded
14 Halted 0 ms 0 KB -