Submission #1085985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085985		underwaterkillerwhale	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	104 ms	4708 KiB

merchant

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e2 + 7;
const int KK = 1e3 + 7;
const int M = 1e4 + 7;
const int Mod = 1e9 + 2022;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;

int n, m, K;
pll a[N][KK];
ll Dist[N][N], dp[N][N];

struct Edge {
    ll u, v, w;
};

ll D[N], Dist2[N][N];

bool Find_positive_cycle (vector<Edge> &edges) {
    rep (i, 1, n) D[i] = 0;
    rep (step, 1, n) {
        iter (&id, edges){
            int u = id.u, v = id.v;
            ll w = id.w;
            if (D[v] < D[u] + w) {
                D[v] = D[u] + w;
            }
        }
    }
    rep (step, 1, n) {
        iter (&id, edges){
            int u = id.u, v = id.v;
            ll w = id.w;
            if (D[v] < D[u] + w) {
                return 1;
            }
        }
    }
    rep (i, 1, n) rep (j, 1, n) Dist2[i][j] = -INF;
    iter (&id, edges) {
        Dist2[id.u][id.v] = id.w;
    }
    rep (k, 1, n)
    rep (i, 1, n)
    rep (j, 1, n) Dist2[i][j] = max(Dist2[i][j], Dist2[i][k] + Dist2[k][j]);
    rep (i, 1, n) rep (j, 1, n) if (i != j && Dist2[i][j] + Dist2[j][i] >= 0) {
        return 1;
    }
    return 0;
}

bool check (ll X) {
    static vector<Edge> edges; edges.clear();
    rep (i, 1, n)
    rep (j, 1, n) {
        if (i != j && Dist[i][j] < INF) {
            edges.pb ({i, j, dp[i][j] - Dist[i][j] * X});
        }
    }
    return Find_positive_cycle (edges);
}

void BS (ll L, ll R) {
    while (L < R)  {
        ll mid = L + R + 1>> 1;
        if (check(mid)) L = mid;
        else R = mid - 1;
    }
    cout << L <<"\n";
}

void solution() {
    cin >> n >> m >> K;
    rep (i, 1, n) {
        rep (j, 1, K ) {
            cin >> a[i][j].fs >> a[i][j].se;
        }
    }
    rep (i, 1, n) rep (j, 1, n) Dist[i][j] = INF;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        Dist[u][v] = w;
    }
    rep (k, 1, n)
    rep (i, 1, n)
    rep (j, 1, n) Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
    bool ok = 0;
    rep (i, 1, n) rep (j, 1, n) if (i != j && Dist[i][j] < INF && Dist[j][i] < INF) {
        ok = 1;
    }
    rep (i, 1, n)
    rep (j, 1, n) {
        rep (k, 1, K) {
            if (a[i][k].fs != -1 && a[j][k].se != -1) {
                dp[i][j] = max(dp[i][j], -a[i][k].fs + a[j][k].se);
            }
        }
    }
    if (!ok) {
        cout << 0 <<"\n";
        return;
    }
//    cout << check(2) <<" a\n";
//    return;
    BS(0, 1e9);
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +5
9 6
7 6
9 1
2 4
4 5
9 2
8 6
9 3
8 1
3
1
6
4
4
2
5
5
6


*/

Compilation message (stderr)

merchant.cpp: In function 'void BS(long long int, long long int)':
merchant.cpp:85:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         ll mid = L + R + 1>> 1;
      |                  ~~~~~~^~~

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