oj.uz

Submission #456320

# Submission time Handle Problem Language Result Execution time Memory
456320 2021-08-06T12:02:44 Z prvocislo Travelling Merchant (APIO17_merchant) C++17
0 / 100
 45 ms 2368 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const ll inf = 1e18 + 5;
const int maxn = 105;
int n, m, k;
void floyd_warshall(vector<vector<ll> >& d)
{
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++)
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
vector<vector<ll> > d(maxn, vector<ll>(maxn, inf)), z(maxn, vector<ll>(maxn, 0)), b(maxn, vector<ll>(maxn)), s(maxn, vector<ll>(maxn));
bool check(ll X) // true ak existuje dobry cyklus (mozeme hladat vyssie)
{
    vector<vector<ll> > dist(n, vector<ll>(n, inf));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i][j] != inf)
        dist[i][j] = X * d[i][j] - z[i][j];
    floyd_warshall(dist);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) 
        if (i != j && dist[i][j] + dist[j][i] <= 0) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) 
        cin >> b[i][j] >> s[i][j];
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int i = 0, u, v, t; i < m; i++)
        cin >> u >> v >> t, d[--u][--v] = t;
    floyd_warshall(d);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && d[i][j] != inf)
        for (int ki = 0; ki < k; ki++) if (b[i][ki] != -1 && s[j][ki] != -1)
            z[i][j] = max(z[i][j], s[j][ki] - b[i][ki]);
    ll lo = 0, hi = 1e9 + 5;
    while (lo < hi)
    {
        ll mi = (lo + hi + 1) >> 1;
        if (check(mi)) lo = mi;
        else hi = mi - 1;
    }
    cout << lo << "\n";
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 2368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 680 KB Output is correct
2 Correct 6 ms 740 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 6 ms 588 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 7 ms 588 KB Output is correct
11 Correct 7 ms 716 KB Output is correct
12 Correct 7 ms 740 KB Output is correct
13 Incorrect 7 ms 716 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 680 KB Output is correct
2 Correct 6 ms 740 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 6 ms 588 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 7 ms 588 KB Output is correct
11 Correct 7 ms 716 KB Output is correct
12 Correct 7 ms 740 KB Output is correct
13 Incorrect 7 ms 716 KB Output isn't correct
14 Halted 0 ms 0 KB -