Submission #887822

#	Time	Username	Problem	Language	Result	Execution time	Memory
887822		Shayan86	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	67 ms	4624 KiB

merchant

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 107;
const ll K = 1007;
const ll inf = 1e9 + 7;

ll n, m, k, b[N][K], s[N][K], dist[N][N], prof[N][N], res[N][N];

vector<pll> adj[N];

void floyd(){
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dist[i][j] = (i == j ? 0 : inf);
    for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) dist[i][j] = w;

    for(int kk = 1; kk <= n; kk++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dist[i][j] = min(dist[i][j], dist[i][kk] + dist[kk][j]);
            }
        }
    }
}

void floyd2(){
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) res[i][j] = inf;
    for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) res[i][j] = w;

    for(int kk = 1; kk <= n; kk++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                res[i][j] = min(res[i][j], res[i][kk] + res[kk][j]);
            }
        }
    }
}

bool check(ll mid){
    for(int i = 1; i <= n; i++) adj[i].clear();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i != j) adj[i].pb({j, (inf / dist[i][j] < mid ? 1e18 : mid * dist[i][j] - prof[i][j])});
        }
    }
    floyd2();

    ll mn = 1;
    for(int i = 1; i <= n; i++) mn = min(mn, res[i][i]);
    return (mn <= 0);
}

int main(){
    fast_io;

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> b[i][j] >> s[i][j];
        }
    }

    int u, v, w;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        adj[u].pb({v, w});
    }

    floyd();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int kk = 1; kk <= k; kk++){
                if(min(s[j][kk], b[i][kk]) != -1) prof[i][j] = max(prof[i][j], s[j][kk] - b[i][kk]);
            }
        }
    }

    ll l = 0, r = inf;
    while(r-l > 1){
        ll mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    cout << l;

}

Compilation message (stderr)

merchant.cpp: In function 'void floyd()':
merchant.cpp:36:42: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) dist[i][j] = w;
      |                                          ^
merchant.cpp: In function 'void floyd2()':
merchant.cpp:49:42: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) res[i][j] = w;
      |                                          ^

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