oj.uz

Submission #165446

# Submission time Handle Problem Language Result Execution time Memory
165446 2019-11-27T10:15:10 Z fedoseevtimofey Travelling Merchant (APIO17_merchant) C++14
0 / 100
 130 ms 3928 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int long long 

const int Inf = 3e9 + 7;

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif 
  int n, m, k;
  cin >> n >> m >> k;
  vector <vector <int>> s(n, vector <int> (k)), b(n, vector <int> (k));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) {
      cin >> b[i][j] >> s[i][j];
    }
  }
  vector <vector <int>> d(n, vector <int> (n, Inf));
  for (int i = 0; i < m; ++i) {
    int u, v, x;
    cin >> u >> v >> x;
    --u, --v;
    d[u][v] = x;
  }
  for (int i = 0; i < n; ++i) d[i][i] = 0;
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  vector <vector <int>> best(n, vector <int> (n, 0));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int id = 0; id < k; ++id) {
        if (s[j][id] != -1 && b[i][id] != -1) best[i][j] = max(best[i][j], s[j][id] - b[i][id]);
      }
    }
  }
  vector <vector <ll>> w(n, vector <ll> (n));
  int l = 0, r = Inf;
  while (r - l > 1) {
    int m = (l + r) >> 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (d[i][j] < Inf) w[i][j] = best[i][j] - (ll)m * d[i][j];
        else w[i][j] = -1e18;
      }
    }
    for (int i = 0; i < n; ++i) w[i][i] = 0;
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          w[i][j] = max(w[i][j], w[i][k] + w[k][j]);
        }
      }
    }
    bool fl = false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j && w[i][j] + w[j][i] >= 0) {
          fl = true;
        }
      }
    }
    if (fl) l = m;
    else r = m;
  }
  cout << l << '\n';
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3448 KB Output is correct
2 Correct 48 ms 632 KB Output is correct
3 Incorrect 47 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 936 KB Output is correct
2 Correct 130 ms 3928 KB Output is correct
3 Correct 53 ms 780 KB Output is correct
4 Correct 58 ms 1008 KB Output is correct
5 Correct 57 ms 1016 KB Output is correct
6 Correct 57 ms 760 KB Output is correct
7 Correct 11 ms 504 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 10 ms 516 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 10 ms 504 KB Output is correct
12 Incorrect 10 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -