Submission #202440

#	Time	Username	Problem	Language	Result	Execution time	Memory
202440		darkkcyan	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	463 ms	3944 KiB

merchant

// vim: foldmethod=marker
// Sat Feb 15 23:04:31 MSK 2020: start 
// Sat Feb 15 23:15:57 MSK 2020: done coding
// Sat Feb 15 23:26:12 MSK 2020: ok samples.
#include <bits/stdc++.h>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }

/*{{{*/
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
int debug = 1;
#define DB(...) stringstream CONCAT(ss, __LINE__); CONCAT(ss, __LINE__) << __VA_ARGS__; debug_block CONCAT(dbbl, __LINE__)(CONCAT(ss, __LINE__).str())
#else
int debug = 0;
#define DB(...)
#endif
int __db_level = 0;
#define clog if (debug) cerr << string(__db_level * 2, ' ')
struct debug_block {
    string name;
    debug_block(const string& name_): name(name_) { clog << "{ " << name << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << name << endl; }
};
#define deb(...) "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]"
#define debln(...)  clog << "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]" << endl
#define _ << ", " <<
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return out << "(" << p.first _ p.second << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return out << "(" << get<0>(t) _ get<1>(t) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return out << "(" << get<0>(t) _ get<1>(t) _ get<2>(t) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) { 
    out << "{";
    if (len(container)) out << container[0];
    rep1(i, len(container) - 1) out _ container[i];
    return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }
/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////

const int maxn = 111;
const int maxk = 1010;
const llong inf = (llong)1e12;
int n, m, k;
llong buy_cost[maxn][maxk], sell_cost[maxn][maxk];
llong dist[maxn][maxn];
llong profit[maxn][maxn];

llong cur_ans[maxn][2];
bool in_queue[maxn][2];
int cnt_vis[maxn][2];

bool check(llong ans) {
    // DB("check " << ans);  
    rep1(i, n) {
        cur_ans[i][0] = cur_ans[i][1] = -inf;
        cnt_vis[i][0] = cnt_vis[i][1] = 0;
        in_queue[i][0] = in_queue[i][1] = false;
    }

    queue<pair<int, int>> qu;
    for (qu.emplace(1, 0), cur_ans[1][0] = 0, in_queue[0][0] = 1; len(qu); qu.pop()) {
        auto [u, holding] = qu.front();
        // DB(deb(u _ holding));  
        ++cnt_vis[u][holding];
        in_queue[u][holding] = false;
        // debln(cnt_vis[u][holding] _ cur_ans[u][holding]);  

        if (cnt_vis[u][holding] > n * 2) return true;
        rep1(v, n) {
            llong new_dist = cur_ans[u][holding] - dist[u][v] * ans;
            if (holding) new_dist += profit[u][v];
            if (new_dist <= cur_ans[v][!holding]) continue;
            cur_ans[v][!holding] = new_dist;
            // debln(v _ !holding _ new_dist _ dist[u][v] _ (-dist[u][v] * ans));  
            if (!in_queue[v][!holding]) {
                qu.emplace(v, !holding);
                in_queue[v][!holding] = true;
            }
        }
    }
    return false;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    // debln(n _ m _ k); 
    rep1(i, n) {
        dist[i][i] = 0;
        for (int f = i + 1; f <= n; ++f)
            dist[i][f] = dist[f][i] = inf;
    }

    rep1(i, n) rep(f, k) {
        cin >> buy_cost[i][f] >> sell_cost[i][f];
    }

    rep(i, m) {
        int u, v; llong d;
        cin >> u >> v >> d;
        dist[u][v] = min(dist[u][v], d);
    }

    rep1(mid, n) rep1(u, n) rep1(v, n) {
        dist[u][v] = min(dist[u][mid] + dist[mid][v], dist[u][v]);
    }

    memset(profit, 0, sizeof(profit));
    rep(thing, k) {
        rep1(u, n) {
            if (buy_cost[u][thing] == -1) continue;
            rep1(v, n) {
                if (sell_cost[v][thing] == -1) continue;
                profit[u][v] = max(profit[u][v], sell_cost[v][thing] - buy_cost[u][thing]);
            }
        }
    }

    llong low = 0, high = 1;
    while (check(high)) high <<= 1;
    while (low < high) {
        llong mid = low + (high - low + 1) / 2;
        if (check(mid)) low = mid;
        else high = mid - 1;
    }
    cout << low;

    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'bool check(long long int)':
merchant.cpp:76:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [u, holding] = qu.front();
              ^

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