oj.uz

Submission #107404

# Submission time Handle Problem Language Result Execution time Memory
107404 2019-04-24T05:53:14 Z kuroni Travelling Merchant (APIO17_merchant) C++14
0 / 100
 70 ms 1368 KB 
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 105, K = 1005;
const long long INF = 4E18 + 7;

int n, m, k, u, v, w[N][N], b[N][K], s[N][K];
long long dis[N][N], tmp[N][N];

bool floyd(long long dis[N][N])
{
    for (int mi = 1; mi <= n; mi++)
        for (int le = 1; le <= n; le++)
            for (int ri = 1; ri <= n; ri++)
                dis[le][ri] = min(dis[le][ri], dis[le][mi] + dis[mi][ri]);
    for (int st = 1; st <= n; st++)
        for (int mi = st + 1; mi <= n; mi++)
            if (dis[st][mi] + dis[mi][st] <= 0)
                return true;
    return false;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
            scanf("%d%d", &b[i][j], &s[i][j]);
        for (int j = 1; j <= n; j++)
            if (j != i)
                dis[i][j] = INF;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int t = 1; t <= k; t++)
                if (b[i][t] != -1 && s[j][t] != -1)
                    w[i][j] = max(w[i][j], s[j][t] - b[i][t]);
    while (m--)
    {
        scanf("%d%d", &u, &v);
        scanf("%lld", &dis[u][v]);
    }
    floyd(dis);
    int le = 1, ri = 1E9;
    while (le <= ri)
    {
        int mi = (le + ri) / 2;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][j] == INF)
                    tmp[i][j] = INF;
                else
                    tmp[i][j] = dis[i][j] * mi - w[i][j];
        if (floyd(tmp))
            le = mi + 1;
        else
            ri = mi - 1;
    }
    printf("%d", ri);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &b[i][j], &s[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
merchant.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &dis[u][v]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1316 KB Output is correct
2 Correct 38 ms 1280 KB Output is correct
3 Incorrect 39 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 10 ms 768 KB Output is correct
8 Correct 9 ms 896 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 12 ms 768 KB Output is correct
12 Correct 10 ms 896 KB Output is correct
13 Incorrect 9 ms 768 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 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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