oj.uz

Submission #974008

# Submission time Handle Problem Language Result Execution time Memory
974008 2024-05-02T15:02:22 Z a_l_i_r_e_z_a Travelling Merchant (APIO17_merchant) C++17
0 / 100
 36 ms 2136 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

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

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 100 + 5, maxk = 1000 + 5;
const ll inf = 1e18 + 7;
ll n, m, K, d[maxn][maxn], df[maxn][maxn], p[maxn][maxn];
ll b[maxn][maxk], s[maxn][maxk];

void floyd(ll adj[maxn][maxn]){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++) smin(adj[i][j], adj[i][k] + adj[k][j]);
        }
    }
}

bool check(int mid){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            df[i][j] = mid * min(d[i][j], inf / mid) - p[i][j];
        }
    }
    floyd(df);
    for(int i = 0; i < n; i++) if(df[i][i] < 0) return 1;
    return 0;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> K;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) if(i != j) d[i][j] = inf;
        for(int k = 0; k < K; k++) cin >> b[i][k] >> s[i][k];
    }
    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        d[u][v] = w;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < K; k++) if(b[i][k] > -1 && s[j][k] > -1){
                smax(p[i][j], s[j][k] - b[i][k]);
            }
        }
    }
    floyd(d);
    ll l = 0, r = 1e9 + 1;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l + 1 << '\n';

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -