Submission #704073

#	Time	Username	Problem	Language	Result	Execution time	Memory
704073		Forested	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	116 ms	4408 KiB

merchant

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

using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n) - 1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003LL;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    } else {
        return false;
    }
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    } else {
        return false;
    }
}

bool has_cycle(i32 n, Vec<Vec<i32>> g) {
    Vec<i32> deg(n);
    REP(i, n) for (i32 j : g[i]) {
        ++deg[j];
    }
    queue<i32> que;
    REP(i, n) {
        if (deg[i] == 0) {
            que.push(i);
        }
    }
    while (!que.empty()) {
        i32 v = que.front();
        que.pop();
        for (i32 u : g[v]) {
            if (--deg[u] == 0) {
                que.push(u);
            }
        }
    }
    return count(ALL(deg), 0) != n;
}

int main() {
    i32 n, m, k;
    cin >> n >> m >> k;
    Vec<Vec<i64>> b(n, Vec<i64>(k)), s(n, Vec<i64>(k));
    REP(i, n) {
        REP(j, k) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    Vec<Vec<pair<i32, i64>>> g(n);
    REP(i, m) {
        i32 u, v, t;
        cin >> u >> v >> t;
        --u;
        --v;
        g[u].emplace_back(v, t);
    }
    
    Vec<Vec<i64>> dist(n, Vec<i64>(n, INF64));
    REP(i, n) {
        dist[i][i] = 0;
        for (auto [j, t] : g[i]) {
            dist[i][j] = t;
        }
    }
    REP(k, n) REP(i, n) REP(j, n) {
        chmin(dist[i][j], dist[i][k] + dist[k][j]);
    }
    
    Vec<Vec<i64>> profit(n, Vec<i64>(n, 0));
    REP(i, n) REP(j, n) REP(l, k) {
        if (b[i][l] != -1 && s[j][l] != -1) {
            chmax(profit[i][j], s[j][l] - b[i][l]);
        }
    }
    
    const auto judge = [&](i64 x) -> bool {
        Vec<Vec<i64>> e(n, Vec<i64>(n, INF64));
        REP(i, n) REP(j, n) {
            if (dist[i][j] != INF64) {
                e[i][j] = x * dist[i][j] - profit[i][j];
            }
        }
        Vec<i64> d(n, 0);
        REP(iter, n) REP(i, n) REP(j, n) {
            if (chmin(d[j], d[i] + e[i][j]) && iter == n - 1) {
                return true;
            }
        }
        Vec<Vec<i32>> g_(n);
        REP(i, n) REP(j, n) {
            if (i != j && d[i] + e[i][j] == d[j]) {
                g_[i].push_back(j);
            }
        }
        return has_cycle(n, g_);
    };
    
    i64 ok = 0, ng = 2LL * INF;
    while (ng - ok > 1) {
        i64 mid = (ok + ng) / 2;
        if (judge(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    
    cout << ok << '\n';
}

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