# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

661156 | 2022-11-24T18:13:40 Z | KING | Travelling Merchant (APIO17_merchant) | C++14 | 79 ms | 4468 KB |

#include<bits/stdc++.h> #define NOT_STONKS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define int long long using namespace std; const int maxn = 100 + 10, maxk = 1e3 + 10; //4e6 + 10; //3e5 + 10; const int mod = 1e9 + 7, inf = 1e18; //998244353; typedef long long ll; ll n, m, k, b[maxn][maxk], s[maxn][maxk], floyd[maxn][maxn], val[maxn][maxn], dis[maxn]; vector< pair<int, int> > G[maxn], adj[maxn]; bool f(ll x) { vector< array<ll, 3> > vec; fill(dis, dis + maxn, inf); dis[1] = 0; for (int v = 1; v <= n; v++) { for (int u = v + 1; u <= n; u++) { vec.push_back({ v, u, (inf / floyd[v][u] < x ? inf : floyd[v][u] * x - val[v][u]) }); vec.push_back({ u, v, (inf / floyd[u][v] < x ? inf : floyd[u][v] * x - val[u][v]) }); } } for (int i = 0; i < n; i++) for (auto [ u, v, w ] : vec) dis[v] = min(dis[v], dis[u] + w); for (auto [ u, v, w ] : vec) if (dis[v] > dis[u] + w) return true; return false; } ll tmp[maxn][maxn]; bool morgh(ll x) { memset(tmp, 63, sizeof tmp); for (int u = 1; u <= n; u++) for (int v = 1; v <= n; v++) if (u != v) tmp[u][v] = min(tmp[u][v], (inf / floyd[u][v] < x ? inf : x * floyd[u][v] - val[u][v])); for (int k = 1; k <= n; k++) { for (int u = 1; u <= n; u++) { for (int v = 1; v <= n; v++) { tmp[u][v] = min(tmp[u][v], tmp[u][k] + tmp[k][v]); } } } for (int i = 1; i <= n; i++) if (tmp[i][i] <= 0) return true; return false; } int32_t main() { NOT_STONKS; cin >> n >> m >> k; for (int i = 1; i <= n; i++) for (int j = 0; j < k; j++) { cin >> b[i][j] >> s[i][j]; } for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({ v, w }); } memset(floyd, 63, sizeof floyd); for (int v = 1; v <= n; v++) for (auto [ u, w ] : adj[v]) floyd[v][u] = min(floyd[v][u], w); for (int k = 1; k <= n; k++) for (int v = 1; v <= n; v++) for (int u = 1; u <= n; u++) floyd[v][u] = min(floyd[v][u], floyd[v][k] + floyd[k][u]); for (int v = 1; v <= n; v++) { for (int u = v + 1; u <= n; u++) { for (int i = 0; i < k; i++) { if (s[u][i] != -1 && b[v][i] != -1) val[v][u] = max(val[v][u], s[u][i] - b[v][i]); if (s[v][i] != -1 && b[u][i] != -1) val[u][v] = max(val[u][v], s[v][i] - b[u][i]); } } } ll high = 1e10, low = -1, mid; while (high - low > 1) { mid = (high + low) >> 1; if (morgh(mid)) low = mid; else high = mid; } cout << low; return 0; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 57 ms | 2004 KB | Output is correct |

2 | Correct | 39 ms | 1312 KB | Output is correct |

3 | Correct | 45 ms | 1236 KB | Output is correct |

4 | Correct | 7 ms | 924 KB | Output is correct |

5 | Correct | 7 ms | 852 KB | Output is correct |

6 | Correct | 7 ms | 924 KB | Output is correct |

7 | Correct | 7 ms | 852 KB | Output is correct |

8 | Correct | 1 ms | 468 KB | Output is correct |

9 | Correct | 10 ms | 924 KB | Output is correct |

10 | Correct | 8 ms | 852 KB | Output is correct |

11 | Correct | 9 ms | 852 KB | Output is correct |

12 | Correct | 1 ms | 596 KB | Output is correct |

13 | Correct | 9 ms | 956 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 7 ms | 924 KB | Output is correct |

2 | Correct | 7 ms | 852 KB | Output is correct |

3 | Correct | 1 ms | 468 KB | Output is correct |

4 | Correct | 10 ms | 924 KB | Output is correct |

5 | Correct | 8 ms | 852 KB | Output is correct |

6 | Correct | 9 ms | 852 KB | Output is correct |

7 | Correct | 1 ms | 596 KB | Output is correct |

8 | Correct | 9 ms | 956 KB | Output is correct |

9 | Correct | 7 ms | 980 KB | Output is correct |

10 | Correct | 7 ms | 852 KB | Output is correct |

11 | Correct | 8 ms | 1012 KB | Output is correct |

12 | Correct | 6 ms | 980 KB | Output is correct |

13 | Correct | 8 ms | 980 KB | Output is correct |

14 | Correct | 1 ms | 468 KB | Output is correct |

15 | Correct | 6 ms | 852 KB | Output is correct |

16 | Correct | 7 ms | 1024 KB | Output is correct |

17 | Correct | 7 ms | 852 KB | Output is correct |

18 | Correct | 6 ms | 980 KB | Output is correct |

19 | Correct | 7 ms | 980 KB | Output is correct |

20 | Correct | 7 ms | 976 KB | Output is correct |

21 | Correct | 7 ms | 980 KB | Output is correct |

22 | Correct | 8 ms | 980 KB | Output is correct |

23 | Correct | 9 ms | 1108 KB | Output is correct |

24 | Correct | 16 ms | 852 KB | Output is correct |

25 | Correct | 8 ms | 980 KB | Output is correct |

26 | Correct | 1 ms | 468 KB | Output is correct |

27 | Correct | 8 ms | 992 KB | Output is correct |

28 | Correct | 8 ms | 980 KB | Output is correct |

29 | Correct | 8 ms | 980 KB | Output is correct |

30 | Correct | 7 ms | 1064 KB | Output is correct |

31 | Correct | 7 ms | 852 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 8 ms | 980 KB | Output is correct |

2 | Correct | 1 ms | 468 KB | Output is correct |

3 | Correct | 8 ms | 992 KB | Output is correct |

4 | Correct | 8 ms | 980 KB | Output is correct |

5 | Correct | 8 ms | 980 KB | Output is correct |

6 | Correct | 7 ms | 1064 KB | Output is correct |

7 | Correct | 7 ms | 852 KB | Output is correct |

8 | Correct | 44 ms | 1492 KB | Output is correct |

9 | Correct | 71 ms | 2200 KB | Output is correct |

10 | Correct | 43 ms | 1468 KB | Output is correct |

11 | Correct | 51 ms | 1516 KB | Output is correct |

12 | Correct | 51 ms | 1488 KB | Output is correct |

13 | Correct | 45 ms | 1456 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 7 ms | 980 KB | Output is correct |

2 | Correct | 7 ms | 852 KB | Output is correct |

3 | Correct | 8 ms | 1012 KB | Output is correct |

4 | Correct | 6 ms | 980 KB | Output is correct |

5 | Correct | 8 ms | 980 KB | Output is correct |

6 | Correct | 1 ms | 468 KB | Output is correct |

7 | Correct | 6 ms | 852 KB | Output is correct |

8 | Correct | 7 ms | 1024 KB | Output is correct |

9 | Correct | 7 ms | 852 KB | Output is correct |

10 | Correct | 6 ms | 980 KB | Output is correct |

11 | Correct | 7 ms | 980 KB | Output is correct |

12 | Correct | 7 ms | 976 KB | Output is correct |

13 | Correct | 7 ms | 980 KB | Output is correct |

14 | Correct | 8 ms | 980 KB | Output is correct |

15 | Correct | 9 ms | 1108 KB | Output is correct |

16 | Correct | 16 ms | 852 KB | Output is correct |

17 | Correct | 44 ms | 1492 KB | Output is correct |

18 | Correct | 71 ms | 2200 KB | Output is correct |

19 | Correct | 43 ms | 1468 KB | Output is correct |

20 | Correct | 51 ms | 1516 KB | Output is correct |

21 | Correct | 51 ms | 1488 KB | Output is correct |

22 | Correct | 45 ms | 1456 KB | Output is correct |

23 | Correct | 8 ms | 980 KB | Output is correct |

24 | Correct | 1 ms | 468 KB | Output is correct |

25 | Correct | 8 ms | 992 KB | Output is correct |

26 | Correct | 8 ms | 980 KB | Output is correct |

27 | Correct | 8 ms | 980 KB | Output is correct |

28 | Correct | 7 ms | 1064 KB | Output is correct |

29 | Correct | 7 ms | 852 KB | Output is correct |

30 | Correct | 57 ms | 2004 KB | Output is correct |

31 | Correct | 39 ms | 1312 KB | Output is correct |

32 | Correct | 45 ms | 1236 KB | Output is correct |

33 | Correct | 7 ms | 924 KB | Output is correct |

34 | Correct | 7 ms | 852 KB | Output is correct |

35 | Correct | 7 ms | 924 KB | Output is correct |

36 | Correct | 7 ms | 852 KB | Output is correct |

37 | Correct | 1 ms | 468 KB | Output is correct |

38 | Correct | 10 ms | 924 KB | Output is correct |

39 | Correct | 8 ms | 852 KB | Output is correct |

40 | Correct | 9 ms | 852 KB | Output is correct |

41 | Correct | 1 ms | 596 KB | Output is correct |

42 | Correct | 9 ms | 956 KB | Output is correct |

43 | Correct | 42 ms | 1364 KB | Output is correct |

44 | Correct | 45 ms | 1492 KB | Output is correct |

45 | Correct | 53 ms | 2592 KB | Output is correct |

46 | Correct | 43 ms | 1492 KB | Output is correct |

47 | Correct | 43 ms | 1632 KB | Output is correct |

48 | Correct | 42 ms | 1620 KB | Output is correct |

49 | Correct | 79 ms | 4052 KB | Output is correct |

50 | Correct | 1 ms | 596 KB | Output is correct |

51 | Correct | 1 ms | 596 KB | Output is correct |

52 | Correct | 42 ms | 1364 KB | Output is correct |

53 | Correct | 45 ms | 1748 KB | Output is correct |

54 | Correct | 44 ms | 1484 KB | Output is correct |

55 | Correct | 46 ms | 1364 KB | Output is correct |

56 | Correct | 40 ms | 1364 KB | Output is correct |

57 | Correct | 1 ms | 476 KB | Output is correct |

58 | Correct | 9 ms | 1136 KB | Output is correct |

59 | Correct | 9 ms | 1124 KB | Output is correct |

60 | Correct | 7 ms | 1120 KB | Output is correct |

61 | Correct | 77 ms | 4468 KB | Output is correct |

62 | Correct | 78 ms | 4404 KB | Output is correct |

63 | Correct | 1 ms | 468 KB | Output is correct |