oj.uz

답안 #923878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923878 2024-02-08T04:11:33 Z awu Passport (JOI23_passport) C++14
16 / 100
 2000 ms 1048576 KB 
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #define int long long
#define ll long long
// #define double long double
#define all(x) x.begin(), x.end()
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
#define f first
#define s second
// #define endl '\n'

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int inf = 1 << 29;
// const ll inf = 1ll << 50;

const int MOD = 1e9 + 7;

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  vector<int> l(n), r(n);
  for(int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
  }
  vector<vector<vector<pii>>> adj(n, vector<vector<pii>>(n + 1));
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j <= n; j++) {
      // adj[i][j - 1].push_back({i, j});
      // adj[min(i, l[j - 1])][max(j, r[j - 1])].push_back({i, j});
      if(i + 1 < j) {
        adj[i][j].push_back({i + 1, j});
        adj[i][j].push_back({i, j - 1});
      }
      adj[i][j].push_back({min(i, l[i]), max(j, r[i])});
      adj[i][j].push_back({min(i, l[j - 1]), max(j, r[j - 1])});
    }
  }
  int q; cin >> q;
  while(q--) {
    int x; cin >> x; x--;
    vector<vector<int>> dist(n, vector<int>(n + 1, inf));
    std::priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    pq.push({0, {x, x + 1}});
    while(pq.size()) {
      auto cur = pq.top(); pq.pop();
      int d = cur.f, i = cur.s.f, j = cur.s.s;
      if(dist[i][j] <= d) continue;
      dist[i][j] = d;
      for(auto nxt : adj[i][j]) {
        pq.push({d + (nxt.s - nxt.f > j - i), nxt});
      }
    }
    int ans = dist[0][n];
    if(ans == inf) ans = -1;
    cout << ans << endl;
  }
  // int q; cin >> q;
  // while(q--) {
  //   int x; cin >> x; x--;
  //   int ans = dist[x][x + 1];
  //   if(ans == inf) ans = -1;
  //   cout << ans << endl;
  // }
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 483 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 816 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 30 ms 5464 KB Output is correct
12 Correct 28 ms 4956 KB Output is correct
13 Correct 34 ms 5464 KB Output is correct
14 Correct 29 ms 5464 KB Output is correct
15 Correct 26 ms 4952 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 816 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 30 ms 5464 KB Output is correct
12 Correct 28 ms 4956 KB Output is correct
13 Correct 34 ms 5464 KB Output is correct
14 Correct 29 ms 5464 KB Output is correct
15 Correct 26 ms 4952 KB Output is correct
16 Execution timed out 2063 ms 379080 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 816 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 30 ms 5464 KB Output is correct
12 Correct 28 ms 4956 KB Output is correct
13 Correct 34 ms 5464 KB Output is correct
14 Correct 29 ms 5464 KB Output is correct
15 Correct 26 ms 4952 KB Output is correct
16 Execution timed out 2063 ms 379080 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 483 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -