Submission #1160537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160537		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1096 ms	3284 KiB

merchant

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

/*SPFA algorithm adapted from https://cp-algorithms.com/graph/bellman_ford.html
Binary Search algorithm adapted from https://cp-algorithms.com/num_methods/binary_search.html
Modifications:
- Transformed state space where each node is (market, item state)
- Total number of states is n * (k + 1)
- k + 1 is item purchases
- vector<ld> dist(v, 0) set to 0
- Start SPFA from only the first market (reduces unnecessary computations)
- Use deque<int> instead of queue<int> for better performance (SLF optimization)
- Limit visitCount threshold to 2 * v for better cycle detection
- if (dist[u] + weight > dist[nextState] + eps) to maximize profit
- Binary search over lambda*/

typedef long long ll;
typedef double ld;

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

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

bool SPFA(ld lambda) {
    ll v = n * (k + 1);
    vector<ld> dist(v, -inf);  // Use -inf instead of 0 for maximization
    vector<int> visitCount(v, 0);
    vector<bool> inQueue(v, false);
    deque<int> q;

    // Start only from the first market (more efficient)
    q.push_back(0);
    dist[0] = 0;
    inQueue[0] = true;
    visitCount[0] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        inQueue[u] = false;

        ll currentMarket = u / (k + 1);
        ll itemState = u % (k + 1);

        if (itemState == 0) {
            for (ll j = 0; j < k; j++) {
                if (b[currentMarket][j] != -1) {
                    ll nextState = currentMarket * (k + 1) + (j + 1);
                    ld weight = -b[currentMarket][j] + eps;

                    if (dist[u] + weight > dist[nextState] + eps) {
                        dist[nextState] = dist[u] + weight;
                        if (!inQueue[nextState]) {
                            if (!q.empty() && dist[nextState] > dist[q.front()])
                                q.push_front(nextState);
                            else
                                q.push_back(nextState);
                            inQueue[nextState] = true;
                            visitCount[nextState]++;
                            if (visitCount[nextState] > 2 * v) return true;
                        }
                    }
                }
            }
        } else {
            ll j = itemState - 1;
            if (s[currentMarket][j] != -1) {
                ll nextState = currentMarket * (k + 1);
                ld weight = s[currentMarket][j] + eps;

                if (dist[u] + weight > dist[nextState] + eps) {
                    dist[nextState] = dist[u] + weight;
                    if (!inQueue[nextState]) {
                        if (!q.empty() && dist[nextState] > dist[q.front()])
                            q.push_front(nextState);
                        else
                            q.push_back(nextState);
                        inQueue[nextState] = true;
                        visitCount[nextState]++;
                        if (visitCount[nextState] > 2 * v) return true;
                    }
                }
            }
        }

        for (auto p : adj[currentMarket]) {
            ll nextMarket = p.first;
            ll travelTime = p.second;
            ll nextState = nextMarket * (k + 1) + itemState;
            ld weight = -lambda * travelTime + eps;

            if (dist[u] + weight > dist[nextState] + eps) {
                dist[nextState] = dist[u] + weight;
                if (!inQueue[nextState]) {
                    if (!q.empty() && dist[nextState] > dist[q.front()])
                        q.push_front(nextState);
                    else
                        q.push_back(nextState);
                    inQueue[nextState] = true;
                    visitCount[nextState]++;
                    if (visitCount[nextState] > 2 * v) return true;
                }
            }
        }
    }
    return false;
}

ll binSearch() {
    ld low = 0.0;
    ld high = 1e12;
    
    for (int iter = 0; iter < 100; iter++) {
        ld mid = (low + high) / 2.0;
        if (SPFA(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    
    return (ll)floor(low);
}

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", binSearch());
    return 0;
}

Compilation message (stderr)

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

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