oj.uz

Submission #915076

# Submission time Handle Problem Language Result Execution time Memory
915076 2024-01-23T09:59:14 Z duckindog Swapping Cities (APIO20_swap) C++14
17 / 100
 1893 ms 29476 KB 
#include<bits/stdc++.h>

using namespace std;

//#define LOCAL

#ifndef LOCAL
#include "swap.h"
#endif // LOCAL

const int N = 1e3 + 10;
int n, m;
vector<pair<int, int>> ad[N];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N; m = M;
  for (int i = 0; i < m; ++i) {
    int u = U[i], v = V[i], w = W[i];
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
}

int f[N][N];
void sktra(int x, int y) {
  memset(f, 63, sizeof f);
  using T = tuple<int, int, int>;
  priority_queue<T, vector<T>, greater<T>> q;
  q.emplace(f[x][y] = 0, x, y);
  while (q.size()) {
    int d, x, y; tie(d, x, y) = q.top(); q.pop();
    if (d != f[x][y]) continue;

    for (auto duck : ad[x]) {
      int v, w; tie(v, w) = duck;
      if (v != y && f[v][y] > max(w, d))
        q.emplace(f[v][y] = max(w, d), v, y);
    }

    for (auto duck : ad[y]) {
      int v, w; tie(v, w) = duck;
      if (v != x && f[x][v] > max(w, d))
        q.emplace(f[x][v] = max(w, d), x, v);

    }
  }

}

int getMinimumFuelCapacity(int X, int Y) {
  sktra(X, Y);
  return f[Y][X] > 1e9 ? -1 : f[Y][X];
}

#ifdef LOCAL
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  int n, m; cin >> n >> m;
  vector<int> U(m), V(m), W(m);
  for (int i = 0; i < m; ++i) cin >> U[i] >> V[i] >> W[i];
  init(n, m, U, V, W);

  int q; cin >> q;
  for (int i = 1; i <= q; ++i) {
    int X, Y; cin >> X >> Y;
    cout << getMinimumFuelCapacity(X, Y) << '\n';
  }


}
#endif // LOCAL

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4312 KB Output is correct
3 Correct 2 ms 4344 KB Output is correct
4 Correct 56 ms 4992 KB Output is correct
5 Correct 246 ms 6572 KB Output is correct
6 Correct 250 ms 6756 KB Output is correct
7 Correct 334 ms 7660 KB Output is correct
8 Correct 311 ms 5904 KB Output is correct
9 Runtime error 20 ms 6232 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4312 KB Output is correct
3 Runtime error 54 ms 11476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4312 KB Output is correct
3 Correct 2 ms 4344 KB Output is correct
4 Correct 56 ms 4992 KB Output is correct
5 Correct 246 ms 6572 KB Output is correct
6 Correct 250 ms 6756 KB Output is correct
7 Correct 334 ms 7660 KB Output is correct
8 Correct 311 ms 5904 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 638 ms 11016 KB Output is correct
11 Correct 654 ms 8340 KB Output is correct
12 Correct 666 ms 10088 KB Output is correct
13 Correct 481 ms 9792 KB Output is correct
14 Correct 555 ms 6804 KB Output is correct
15 Correct 655 ms 5960 KB Output is correct
16 Correct 623 ms 6948 KB Output is correct
17 Correct 622 ms 6996 KB Output is correct
18 Correct 760 ms 11932 KB Output is correct
19 Correct 424 ms 10428 KB Output is correct
20 Correct 674 ms 10400 KB Output is correct
21 Correct 923 ms 15640 KB Output is correct
22 Correct 151 ms 8964 KB Output is correct
23 Correct 531 ms 9872 KB Output is correct
24 Correct 1709 ms 29476 KB Output is correct
25 Correct 1415 ms 18880 KB Output is correct
26 Correct 1893 ms 29064 KB Output is correct
27 Correct 625 ms 7188 KB Output is correct
28 Correct 1745 ms 28020 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4312 KB Output is correct
4 Correct 2 ms 4344 KB Output is correct
5 Correct 56 ms 4992 KB Output is correct
6 Correct 246 ms 6572 KB Output is correct
7 Correct 250 ms 6756 KB Output is correct
8 Correct 334 ms 7660 KB Output is correct
9 Correct 311 ms 5904 KB Output is correct
10 Runtime error 20 ms 6232 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4312 KB Output is correct
3 Correct 2 ms 4344 KB Output is correct
4 Correct 56 ms 4992 KB Output is correct
5 Correct 246 ms 6572 KB Output is correct
6 Correct 250 ms 6756 KB Output is correct
7 Correct 334 ms 7660 KB Output is correct
8 Correct 311 ms 5904 KB Output is correct
9 Runtime error 20 ms 6232 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4312 KB Output is correct
4 Correct 2 ms 4344 KB Output is correct
5 Correct 56 ms 4992 KB Output is correct
6 Correct 246 ms 6572 KB Output is correct
7 Correct 250 ms 6756 KB Output is correct
8 Correct 334 ms 7660 KB Output is correct
9 Correct 311 ms 5904 KB Output is correct
10 Runtime error 20 ms 6232 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -