QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604352#5073. Elden RingAngelOlanWA 200ms3764kbC++202.3kb2024-10-02 10:14:352024-10-02 10:14:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 10:14:35]
  • 评测
  • 测评结果:WA
  • 用时:200ms
  • 内存:3764kb
  • [2024-10-02 10:14:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// Pura Gente del Coach Moy
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

#define pb push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define ROF(i, a, b) for (int i = (int)a - 1; i >= (int)b; --i)
#define ENDL '\n'

constexpr int INF = 1e9 + 5;

void solve_less_eq(int A, int B, vector<vi>& g, vi& a) {
  int N = SZ(g);
  vi d(N, -1);
  d[0] = 0;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &v : g[u]) if (d[v] == -1 && (ll)A * d[u] + a[0] > (ll)B * d[u] + a[v]) {
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  cout << d[N - 1] << ENDL;
}

int find_max_time(int D, vector<vi>& g, vi& a) {
  int N = SZ(g), t = -1;
  vi vis(N);
  vis[0] = 1;
  priority_queue<pi> pq;
  pq.push({1, 0});
  while (!pq.empty() && -pq.top().first <= t) {
    int u = pq.top().second;
    pq.pop();
    for (auto &v : g[u]) if (!vis[v]) {
      vis[v] = 1;
      int dv = a[v] <= a[0] ? 0 : ((a[v] - a[0]) / D + 1);
      pq.push({-dv, v});
    }
    ++t;
  }
  return t;
}

void solve_greater(int D, vector<vi>& g, vi& a) {
  int N = SZ(g);
  vi d(N, INF);
  d[0] = 0;
  priority_queue<pi> pq;
  pq.push({0, 0});
  int mx_time = find_max_time(D, g, a);
  while (!pq.empty()) {
    auto [du, u] = pq.top();
    du = -du;
    pq.pop();
    if (du > d[u]) continue;
    for (auto &v : g[u]) {
      int y = a[v] <= a[0] ? 0 : ((a[v] - a[0]) / D + 1);
      int dx = max(du, y);
      if (dx <= mx_time && dx + 1 < d[v]) {
        d[v] = dx + 1; 
        pq.push({-d[v], v});
      }
    }
  }
  if (d[N - 1] == INF) d[N - 1] = -1;
  cout << d[N - 1] << ENDL;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  int t;
  cin >> t;
  while (t--) {
    int N, M, A, B;
    cin >> N >> M >> A >> B;
    vector<vi> g(N);
    while (M--) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      g[u].pb(v), g[v].pb(u);
    }
    vi a(N);
    FOR (i, 0, N) {
      cin >> a[i];
      if (i) a[i] += B;
    }
    if (A <= B) solve_less_eq(A, B, g, a);
    else solve_greater(A - B, g, a);
  }

  return 0;
} 

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: 0
Accepted
time: 184ms
memory: 3504kb

input:

100000
6 10 107812 105568
6 5
3 6
4 6
4 2
5 1
5 6
4 5
1 3
1 2
2 5
124065 140875 29890 80077 116532 35394
9 10 82107 88302
1 2
2 3
5 3
5 1
1 4
9 6
3 5
8 2
5 6
7 5
22670 3735 33660 92823 139960 89319 83335 158330 117349
6 10 181257 173221
5 3
3 4
3 1
5 1
2 1
3 6
3 1
6 2
3 6
4 3
76902 46253 123092 2661...

output:

-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 192ms
memory: 3628kb

input:

100000
10 10 7791 61545
9 3
3 10
7 4
2 1
3 4
2 6
8 2
2 3
5 2
3 2
142757 98694 34871 181188 28671 62924 172723 13856 11576 26661
10 10 194165 132103
2 5
8 7
3 1
7 3
1 2
6 1
4 9
1 3
4 3
10 4
176824 47360 148701 4531 66460 199228 135267 149448 65763 125940
9 10 152778 128023
3 1
3 2
1 2
1 6
5 7
5 2
4 7...

output:

-1
-1
7
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
4
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
1
3
-1
-1
1
1
-1
-1
-1
5
1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 188ms
memory: 3656kb

input:

10000
95 100 88670 88078
80 65
52 30
18 23
62 56
2 1
11 20
69 32
65 35
44 92
38 14
81 89
19 3
15 46
2 24
85 6
8 21
59 51
27 17
17 33
25 23
44 12
63 57
29 9
36 34
9 81
3 8
41 11
58 93
42 15
12 15
17 14
16 73
21 60
94 21
87 5
6 67
91 43
18 8
23 54
83 69
82 79
23 95
26 47
46 8
22 21
9 5
30 5
50 14
56 5...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 195ms
memory: 3764kb

input:

10000
55 100 45240 42375
2 30
41 35
44 42
20 27
25 7
43 22
14 12
25 48
2 1
48 39
22 55
28 4
13 21
2 5
27 2
18 42
18 52
34 13
50 6
6 47
6 5
37 5
35 36
31 23
12 24
1 44
9 3
9 1
7 35
26 45
44 48
27 49
40 43
34 9
43 47
26 42
49 28
53 31
11 32
8 6
22 27
23 32
6 54
1 16
22 11
34 20
21 44
31 2
9 22
23 5
1 ...

output:

-1
-1
-1
4
5
-1
6
-1
13
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
7
-1
-1
4
-1
12
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
1
18
-1
14
5
5
-1
-1
3
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
14
15
-1
-1
-1
-1
-1
-1
-...

result:

ok 10000 numbers

Test #6:

score: -100
Wrong Answer
time: 200ms
memory: 3624kb

input:

10000
78 100 3273 35629
51 26
12 13
60 57
67 56
34 9
7 44
3 6
63 5
6 75
49 36
63 36
9 10
10 20
8 16
58 29
10 41
4 5
4 78
35 70
68 72
11 3
20 66
18 2
14 25
21 22
52 18
21 23
24 43
51 32
19 49
38 37
28 54
9 73
24 30
21 32
10 40
4 29
4 67
55 32
27 33
38 39
13 37
4 68
20 26
73 37
60 67
4 9
15 41
12 1
2 ...

output:

-1
2
-1
-1
-1
-1
-1
3
-1
-1
6
2
-1
-1
-1
-1
-1
4
-1
-1
17
-1
5
5
8
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
2
9
-1
-1
6
-1
-1
-1
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
3
6
5
-1
-1
3
-1
-1
-1
-1
3
3
-1
4
-1
-1
5
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
7
7
-1
-1
3
-1
-1
-1
1...

result:

wrong answer 3678th numbers differ - expected: '-1', found: '5'