Submission #1160514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160514		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1095 ms	3496 KiB

merchant

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

typedef long long ll;
typedef double ld;

const ll MAX_N = 100;
const ll MAX_K = 1000;
const ld INF = 1e18;

ll N, M, K;
vector<vector<pair<ll, ll>>> adj; // (market, time)
vector<vector<ll>> B, S;

bool check(ld lambda) {
    ll V = N * (K + 1);
    vector<ld> dist(V, -INF);
    vector<int> cnt(V, 0);
    vector<bool> inQ(V, true);
    queue<int> q;

    for (int i = 0; i < V; i++) {
        dist[i] = 0;
        q.push(i);
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inQ[node] = false;

        ll u = node / (K + 1);
        ll c = (node % (K + 1)) - 1;

        if (c == -1) { // Empty backpack
            for (ll j = 0; j < K; j++) {
                if (B[u][j] != -1) {
                    ll next = u * (K + 1) + (j + 1);
                    ld w = -B[u][j];
                    if (dist[node] + w > dist[next]) {
                        dist[next] = dist[node] + w;
                        if (!inQ[next]) {
                            q.push(next);
                            inQ[next] = true;
                            cnt[next]++;
                            if (cnt[next] > V) return true;
                        }
                    }
                }
            }
        } else { // Carrying item j
            ll j = c;
            if (S[u][j] != -1) {
                ll next = u * (K + 1);
                ld w = S[u][j];
                if (dist[node] + w > dist[next]) {
                    dist[next] = dist[node] + w;
                    if (!inQ[next]) {
                        q.push(next);
                        inQ[next] = true;
                        cnt[next]++;
                        if (cnt[next] > V) return true;
                    }
                }
            }
        }

        // Move
        for (auto [v, T_p] : adj[u]) {
            ll next = v * (K + 1) + (c + 1);
            ld w = -lambda * T_p;
            if (dist[node] + w > dist[next]) {
                dist[next] = dist[node] + w;
                if (!inQ[next]) {
                    q.push(next);
                    inQ[next] = true;
                    cnt[next]++;
                    if (cnt[next] > V) return true;
                }
            }
        }
    }
    return false;
}

ll solve() {
    ld lo = 0.0, hi = 1e12;
    for (int iter = 0; iter < 100; iter++) {
        ld mid = (lo + hi) / 2.0;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    if (!check(lo)) return 0;
    return floor(lo);
}

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 v, w, t;
        scanf("%lld %lld %lld", &v, &w, &t);
        adj[v-1].emplace_back(w-1, t);
    }

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

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%lld %lld %lld", &N, &M, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |             scanf("%lld %lld", &B[i][j], &S[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%lld %lld %lld", &v, &w, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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