oj.uz

Submission #795121

# Submission time Handle Problem Language Result Execution time Memory
795121 2023-07-27T06:49:43 Z andecaandeci Cyberland (APIO23_cyberland) C++17
100 / 100
 1227 ms 15304 KB 
#include<bits/stdc++.h>
using namespace std;
const double INF=1e18;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
  k=min(k, 100);
  vector<vector<pair<int, double>>> adj(n);
  for(int i=0; i<m; i++) {
    adj[x[i]].push_back({y[i], c[i]});
    adj[y[i]].push_back({x[i], c[i]});
  }
  vector<double> dist(n), temp(n); 
  for(auto &p : dist) p=INF;
  for(auto &p : temp) p=INF;
  priority_queue<pair<double, int>> pq;
  double ans=INF; temp[0]=0.;
  for(int j=0; j<=k; j++) {
    vector<double> temp(n); for(double &p : temp) p=INF;
    if(j) {
      for(int i=0; i<n; i++) {
        if(a[i]==1 || dist[i]==INF) continue;
        if(a[i]==0) temp[i]=0;
        pq.push({-dist[i]/2., i});
      }
    } else pq.push({0., 0});
    while(!pq.empty()) {
      auto [cur, u]=pq.top(); cur=-cur;
      pq.pop();
      if(u==h) continue;
      for(auto [v, w] : adj[u]) {
        if(temp[v]>cur+w) {
          if(a[v]==0) temp[v]=0.;
          else temp[v]=cur+w;
          pq.push({-temp[v], v});
        }
      }
    }
    ans=min(ans, temp[h]);
    if(j==0 && temp[h]==INF) break;
    swap(temp, dist);
  }
  return (ans<INF ? ans : -1.);
}
/*int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m, k, h; cin >> n >> m >> k >> h;
  vector<int> x(m), y(m), c(m), a(n);
  for(int &p : x) cin >> p;
  for(int &p : y) cin >> p;
  for(int &p : c) cin >> p;
  for(int &p : a) cin >> p;
  cout << solve(n, m, k, h, x, y, c, a) << '\n';
  return 0;
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 444 KB Correct.
2 Correct 21 ms 732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 836 KB Correct.
2 Correct 25 ms 1440 KB Correct.
3 Correct 29 ms 1356 KB Correct.
4 Correct 25 ms 1364 KB Correct.
5 Correct 25 ms 1356 KB Correct.
6 Correct 20 ms 2332 KB Correct.
7 Correct 27 ms 2452 KB Correct.
8 Correct 16 ms 3380 KB Correct.
9 Correct 24 ms 1076 KB Correct.
10 Correct 24 ms 1108 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1260 KB Correct.
2 Correct 129 ms 1308 KB Correct.
3 Correct 117 ms 1296 KB Correct.
4 Correct 72 ms 644 KB Correct.
5 Correct 76 ms 1200 KB Correct.
6 Correct 41 ms 1716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9000 KB Correct.
2 Correct 114 ms 1280 KB Correct.
3 Correct 95 ms 1352 KB Correct.
4 Correct 101 ms 1308 KB Correct.
5 Correct 68 ms 1204 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1324 KB Correct.
2 Correct 24 ms 1300 KB Correct.
3 Correct 22 ms 1276 KB Correct.
4 Correct 21 ms 2240 KB Correct.
5 Correct 20 ms 1112 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1268 KB Correct.
2 Correct 50 ms 1228 KB Correct.
3 Correct 39 ms 11680 KB Correct.
4 Correct 68 ms 1876 KB Correct.
5 Correct 44 ms 1128 KB Correct.
6 Correct 62 ms 976 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1340 KB Correct.
2 Correct 18 ms 596 KB Correct.
3 Correct 348 ms 14996 KB Correct.
4 Correct 238 ms 5300 KB Correct.
5 Correct 392 ms 10864 KB Correct.
6 Correct 177 ms 8476 KB Correct.
7 Correct 229 ms 4532 KB Correct.
8 Correct 190 ms 2412 KB Correct.
9 Correct 88 ms 1348 KB Correct.
10 Correct 79 ms 1320 KB Correct.
11 Correct 166 ms 2460 KB Correct.
12 Correct 116 ms 1136 KB Correct.
13 Correct 98 ms 1284 KB Correct.
14 Correct 208 ms 8020 KB Correct.
15 Correct 204 ms 3760 KB Correct.
16 Correct 89 ms 1340 KB Correct.
17 Correct 116 ms 1536 KB Correct.
18 Correct 98 ms 1468 KB Correct.
19 Correct 301 ms 2360 KB Correct.
20 Correct 5 ms 468 KB Correct.
21 Correct 8 ms 468 KB Correct.
22 Correct 14 ms 1108 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 1152 KB Correct.
2 Correct 50 ms 596 KB Correct.
3 Correct 253 ms 15304 KB Correct.
4 Correct 281 ms 3248 KB Correct.
5 Correct 1222 ms 11100 KB Correct.
6 Correct 505 ms 8648 KB Correct.
7 Correct 537 ms 7444 KB Correct.
8 Correct 240 ms 2572 KB Correct.
9 Correct 222 ms 1352 KB Correct.
10 Correct 193 ms 1360 KB Correct.
11 Correct 164 ms 1472 KB Correct.
12 Correct 261 ms 1472 KB Correct.
13 Correct 241 ms 1604 KB Correct.
14 Correct 1227 ms 8948 KB Correct.
15 Correct 956 ms 8756 KB Correct.
16 Correct 395 ms 4308 KB Correct.
17 Correct 290 ms 2672 KB Correct.
18 Correct 219 ms 1360 KB Correct.
19 Correct 313 ms 1528 KB Correct.
20 Correct 243 ms 1544 KB Correct.
21 Correct 860 ms 552 KB Correct.
22 Correct 10 ms 436 KB Correct.
23 Correct 15 ms 316 KB Correct.
24 Correct 38 ms 980 KB Correct.