Submission #349737

#	Time	Username	Problem	Language	Result	Execution time	Memory
349737		TAMREF	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	101 ms	4204 KiB

merchant

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, k;
const ll inf = 1e15;
ll sp[105][105], rv[105][105];
ll tsp[105][105];
vector<ll> B[105], S[105];

pll operator+ (pll u, const pll v){
    return pll(u.va + v.va, u.vb + v.vb);
}

bool pro(ll x){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j || sp[i][j] > 1e9 + 10){
                tsp[i][j] = 1e18;
                continue;
            }
            tsp[i][j] = sp[i][j] * x - rv[i][j];
        }
    }
    for(int t = 1; t <= n; t++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                tsp[i][j] = min(tsp[i][j], tsp[i][t] + tsp[t][j]);
            }
        }
    }
    debug("-------tsp------x = %lld----\n",x);
    for(int i = 1; i <= n; i++){
        for(int j =1 ; j <= n; j++){
            debug("%lld ",tsp[i][j]);
        }
        debug("\n");
    }
    for(int i = 1; i <= n; i++) if(tsp[i][i] <= 0) return true;
    return false;
}

int main(){
    fio;
    cin >> n >> m >> k; 
    for(int i = 1; i <= n; i++){
        fill(sp[i] + 1, sp[i] + n + 1, inf);
        sp[i][i] = 0;
        B[i] = vector<ll>(k + 1);
        S[i] = vector<ll>(k + 1);
        for(int j = 1; j <= k; j++){
            cin >> B[i][j] >> S[i][j];
        }
    }
    for(ll i = 1, a, b, w; i <= m; i++){
        cin >> a >> b >> w;
        sp[a][b] = min(w, sp[a][b]);
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                sp[i][j] = min(sp[i][j], sp[i][k] + sp[k][j]);
            }
        }
    }
    debug("-------sp----------\n");
    for(int i = 1; i <= n; i++){
        for(int j =1 ; j <= n; j++){
            debug("%lld ",sp[i][j]);
        }
        debug("\n");
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int t = 0; t <= k; t++){
                if(B[i][t] == -1 || S[j][t] == -1) continue;
                rv[i][j] = max(rv[i][j], S[j][t] - B[i][t]);
            }
        }
    }
    ll lo = 0, mi, hi = 1e9 + 5;
    while(lo < hi){
        mi = (lo + hi + 1) >> 1;
        if(pro(mi)) lo = mi;
        else hi = mi - 1;
    }
    cout << lo << '\n';
}

Compilation message (stderr)

merchant.cpp: In function 'bool pro(ll)':
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:61:5: note: in expansion of macro 'debug'
   61 |     debug("-------tsp------x = %lld----\n",x);
      |     ^~~~~
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:64:13: note: in expansion of macro 'debug'
   64 |             debug("%lld ",tsp[i][j]);
      |             ^~~~~
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:66:9: note: in expansion of macro 'debug'
   66 |         debug("\n");
      |         ^~~~~
merchant.cpp: In function 'int main()':
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:95:5: note: in expansion of macro 'debug'
   95 |     debug("-------sp----------\n");
      |     ^~~~~
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:98:13: note: in expansion of macro 'debug'
   98 |             debug("%lld ",sp[i][j]);
      |             ^~~~~
merchant.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
merchant.cpp:100:9: note: in expansion of macro 'debug'
  100 |         debug("\n");
      |         ^~~~~

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