Submission #1160546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160546		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	Compilation error	0 ms	0 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<ld> dist(v, -inf);
    
    // Initialize starting states (no item at each market)
    for (ll u = 0; u < n; u++) {
        dist[u * (k + 1)] = 0; // No item state
    }
    
    // Bellman-Ford: V-1 relaxations
    for (ll iter = 0; iter < v - 1; iter++) {
        bool updated = false;
        for (ll u = 0; u < n; u++) {
            ll uNoItem = u * (k + 1);
            // Buy an item
            for (ll j = 0; j < k; j++) {
                if (b[u][j] != -1) {
                    ll uWithJ = u * (k + 1) + (j + 1);
                    ld weight = -b[u][j];
                    if (dist[uNoItem] > -inf && dist[uNoItem] + weight > dist[uWithJ] + eps) {
                        dist[uWithJ] = dist[uNoItem] + weight;
                        updated = true;
                    }
                }
            }
            // Sell an item
            for (ll j = 0; j < k; j++) {
                ll uWithJ = u * (k + 1) + (j + 1);
                if (s[u][j] != -1 && dist[uWithJ] > -inf) {
                    ld weight = s[u][j];
                    if (dist[uWithJ] + weight > dist[uNoItem] + eps) {
                        dist[uNoItem] = dist[uWithJ] + weight;
                        updated = true;
                    }
                }
            }
            // Move with current item state
            for (auto p : adj[u]) {
                ll vMarket = p.first;
                ll travelTime = p.second;
                for (ll c = 0; c <= k; c++) {
                    ll uState = u * (k + 1) + c;
                    ll vState = vMarket * (k + 1) + c;
                    ld weight = -lambda * travelTime;
                    if (dist[uState] > -inf && dist[uState] + weight > dist[vState] + eps) {
                        dist[vState] = dist[uState] + weight;
                        updated = true;
                    }
                }
            }
        }
        if (!updated) break; // Early exit if no changes
    }
    
    // Check for positive cycles
    for (ll u = 0; u < n; u++) {
        ll uNoItem = u * (k + 1);
        for (ll j = 0; j < k; j++) {
            if (b[u][j] != -1) {
                ll uWithJ = u * (k + 1) + (j + 1);
                ld weight = -b[u][j];
                if (dist[uNoItem] + weight > dist[uWithJ] + eps) {
                    return true;
                }
            }
            ll uWithJ = u * (k + 1) + (j + 1);
            if (s[u][j] != -1 && dist[uWithJ] > -inf) {
                ld weight = s[u][j];
                if (dist[uWithJ] + weight > dist[uNoItem] + eps) {
                    return true;
                }
            }
        }
        for (auto p : adj[u]) {
            ll vMarket = p.first;
            ll travelTime = p.second;
            for (ll c = 0; c <= k; c++) {
                ll uState = u * (k + 1) + c;
                ll vState = vMarket * (k + 1) + c;
                ld weight = -lambda * travelTime;
                if (dist[uState] > -inf && dist[uState] + weight > dist[vState] + eps) {
                    return true;
                }
            }
        }
    }
    return false;
}

ll solve() {
    ld low = 0.0;
    ld high = 1e12;
    for (int iter = 0; iter < 50; iter++) { // Reduced to 50 for speed
        ld mid = (low + high) / 2.0;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    if (!check(low)) return 0;
    return (ll)floor(low + eps); // Ensure rounding handles floating-point precision
}

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

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:123:16: error: expected primary-expression at end of input
  123 |     s.assign(n,
      |                ^
merchant.cpp:123:16: error: expected '}' at end of input
merchant.cpp:120:12: note: to match this '{'
  120 | int main() {
      |            ^
merchant.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~