Submission #572746

#	Time	Username	Problem	Language	Result	Execution time	Memory
572746		timreizin	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	877 ms	3296 KiB

merchant

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <set>
#include <array>
#include <algorithm>
#include <cassert>
#include <stack>

using namespace std;

using ll = long long;

const ll INF = 1e18;
const __int128 LINF = 1e35;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<ll, ll>>> costs(n, vector<pair<ll, ll>>(k));
    for (int i = 0; i < n; ++i) for (auto &[b, s] : costs[i]) cin >> b >> s;
    vector<vector<ll>> adj(n, vector<ll>(n, INF));
    while (m--)
    {
        int v, w;
        ll t;
        cin >> v >> w >> t;
        --v;
        --w;
        adj[v][w] = t;
    }
    for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    vector<vector<pair<ll, ll>>> graph(2 * n, vector<pair<ll, ll>>(2 * n, {-1, -1}));
    for (int i = 0; i < n; ++i)
    {
        graph[i * 2 + 1][i * 2] = {0, 0};
        for (int j = 0; j < n; ++j)
        {
            //i->j
            if (adj[i][j] == INF) continue;
            graph[i * 2 + 1][j * 2] = {0, adj[i][j]};
            ll maxProfit = 0;
            for (int k = 0; k < costs[i].size(); ++k) if (costs[i][k].first != -1) maxProfit = max(maxProfit, costs[j][k].second - costs[i][k].first);
            graph[i * 2][j * 2 + 1] = {maxProfit, adj[i][j]};
        }
    }
    auto check = [&graph](ll m) -> bool
    {
        vector<vector<__int128>> adj(graph.size(), vector<__int128>(graph.size(), -LINF));
        for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (graph[i][j].first != -1) adj[i][j] = graph[i][j].first - m * graph[i][j].second;
        for (int k = 0; k < graph.size(); ++k) for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (adj[i][k] != -LINF && adj[k][j] != -LINF) adj[i][j] = min(max(adj[i][j], adj[i][k] + adj[k][j]), LINF);
        for (int i = 0; i < graph.size(); ++i) if (adj[i][i] >= 0) return true;
        return false;
    };
    ll l = 1, r = 1e10;
    while (l < r)
    {
        //first with x with no ans >= x
        ll m = (l + r) >> 1;
        if (check(m)) l = m + 1;
        else r = m;
    }
    cout << l - 1;
    return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for (int k = 0; k < costs[i].size(); ++k) if (costs[i][k].first != -1) maxProfit = max(maxProfit, costs[j][k].second - costs[i][k].first);
      |                             ~~^~~~~~~~~~~~~~~~~
merchant.cpp: In lambda function:
merchant.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (graph[i][j].first != -1) adj[i][j] = graph[i][j].first - m * graph[i][j].second;
      |                         ~~^~~~~~~~~~~~~~
merchant.cpp:53:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (graph[i][j].first != -1) adj[i][j] = graph[i][j].first - m * graph[i][j].second;
      |                                                                ~~^~~~~~~~~~~~~~
merchant.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int k = 0; k < graph.size(); ++k) for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (adj[i][k] != -LINF && adj[k][j] != -LINF) adj[i][j] = min(max(adj[i][j], adj[i][k] + adj[k][j]), LINF);
      |                         ~~^~~~~~~~~~~~~~
merchant.cpp:54:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int k = 0; k < graph.size(); ++k) for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (adj[i][k] != -LINF && adj[k][j] != -LINF) adj[i][j] = min(max(adj[i][j], adj[i][k] + adj[k][j]), LINF);
      |                                                                ~~^~~~~~~~~~~~~~
merchant.cpp:54:105: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int k = 0; k < graph.size(); ++k) for (int i = 0; i < graph.size(); ++i) for (int j = 0; j < graph.size(); ++j) if (adj[i][k] != -LINF && adj[k][j] != -LINF) adj[i][j] = min(max(adj[i][j], adj[i][k] + adj[k][j]), LINF);
      |                                                                                                       ~~^~~~~~~~~~~~~~
merchant.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < graph.size(); ++i) if (adj[i][i] >= 0) return true;
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34