Submission #1160548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160548		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1123 ms	1114112 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;

const ll maxN = 100;
const ll maxK = 1000;
const ld inf = 1e18;
const ld eps = 1e-9;

ll n, m, k;
vector<vector<pair<ll, ll>>> adj;
vector<vector<ll>> b, s;

bool check(ld lambda) {
    ll v = n * (k + 1);
    vector<vector<ld>> dist(v, vector<ld>(v, -inf));
    
    // Initialize self-loops and starting states
    for (ll u = 0; u < n; u++) {
        ll uNoItem = u * (k + 1);
        dist[uNoItem][uNoItem] = 0; // No item state
    }
    
    // Build edges
    for (ll u = 0; u < n; u++) {
        ll uNoItem = u * (k + 1);
        // Buy transitions
        for (ll j = 0; j < k; j++) {
            if (b[u][j] != -1) {
                ll uWithJ = u * (k + 1) + (j + 1);
                dist[uNoItem][uWithJ] = -b[u][j] + eps;
            }
        }
        // Sell transitions
        for (ll j = 0; j < k; j++) {
            ll uWithJ = u * (k + 1) + (j + 1);
            if (s[u][j] != -1) {
                dist[uWithJ][uNoItem] = s[u][j] + eps;
            }
        }
        // Move transitions
        for (auto p : adj[u]) {
            ll v = p.first;
            ll t = p.second;
            for (ll c = 0; c <= k; c++) {
                ll uState = u * (k + 1) + c;
                ll vState = v * (k + 1) + c;
                dist[uState][vState] = -lambda * t + eps;
            }
        }
    }
    
    // Floyd-Warshall for cycle detection
    for (ll k = 0; k < v; k++) {
        for (ll i = 0; i < v; i++) {
            for (ll j = 0; j < v; j++) {
                if (dist[i][k] > -inf && dist[k][j] > -inf) {
                    ld newDist = dist[i][k] + dist[k][j];
                    if (newDist > dist[i][j] + eps) {
                        dist[i][j] = newDist;
                    }
                }
            }
        }
    }
    
    // Check for positive cycles (self-loops or reachable cycles)
    for (ll i = 0; i < v; i++) {
        if (dist[i][i] > eps) {
            return true;
        }
    }
    return false;
}

ll solve() {
    ld low = 0.0;
    ld high = 1e9; // Tightened upper bound based on constraints
    for (int iter = 0; iter < 30; iter++) { // Reduced iterations
        ld mid = (low + high) / 2.0;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    if (!check(low)) return 0;
    return (ll)floor(low + eps);
}

int main() {
    scanf("%lld %lld %lld", &n, &m, &k);
    b.assign(n, vector<ll>(k));
    s.assign(n, vector<ll>(k));
    adj.resize(n);

    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < k; j++) {
            scanf("%lld %lld", &b[i][j], &s[i][j]);
        }
    }

    for (ll i = 0; i < m; i++) {
        ll from, to, time;
        scanf("%lld %lld %lld", &from, &to, &time);
        adj[from - 1].emplace_back(to - 1, time);
    }

    printf("%lld\n", solve());
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |             scanf("%lld %lld", &b[i][j], &s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%lld %lld %lld", &from, &to, &time);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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