oj.uz

Submission #591254

# Submission time Handle Problem Language Result Execution time Memory
591254 2022-07-07T06:58:44 Z codebuster_10 Travelling Merchant (APIO17_merchant) C++17
100 / 100
 464 ms 3424 KB 
#include <bits/stdc++.h>
// #define int int64_t //be careful about this 

using namespace std;

#define vt vector 
#define ar array 
#define pr pair 

#define f first 
#define s second

#define pb push_back
#define eb emplace_back

#define fr(i,a,b) for(int i = (a); i < (b); ++i)
#define rf(i,a,b) for(int i = (b)-1; i >= (a); --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace IN{
  template<class T> void re(vector<T> &A);
  template<class S,class T> void re(pair<S,T> &A);
  template<class T,size_t N> void re(array<T,N> &A);

  template<class T> void re(T& x){ 
    cin >> x;}
  template<class H, class... T> void re(H& h, T&... t){ 
    re(h); re(t...);}

  template<class T> void re(vector<T> &A){ 
    for(auto& x : A) re(x);}
  template<class S,class T> void re(pair<S,T> &A){ 
      re(A.first); re(A.second);}
  template<class T,size_t N> void re(array<T,N> &A){
    for(int i = 0; i < N; ++i)  re(A[i]);}
}

namespace OUT{
  template<class T>
  void __p(const T& a){ cout<<a; }
  template<class T, class F>
  void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
  template<class T, size_t N>
  void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
  template<class T>
  void __p(const vector<T>& a){
    cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
  template<class T, class ...Arg>
  void __p(T a1, Arg ...a){__p(a1); __p(a...); }
  template<class Arg1>
  void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
  template<class Arg1, class ... Args>
  void __f(const char *ss, Arg1 &&arg1, Args &&... args){
    int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
    const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUNC{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
#endif
  }

  template<class T> bool ckmin(T& a, const T& b){ 
    return b < a ? a = b, true : false; }
    
  template<class T> bool ckmax(T& a, const T& b){ 
    return a < b ? a = b, true : false; }

  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  int my_rand(int L, int R){ 
    return uniform_int_distribution<int>(L,R)(rng); }
  
  template<class T> int sz(const T& x){ 
    return int(x.size()); }

  template<class T> int lb(const vector<T>& vec,const T& val){
    return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  template<class T> int ub(const vector<T>& vec,const T& val){
    return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  constexpr int  dx[4] = {1,0,-1,0};
  constexpr int  dy[4] = {0,1,0,-1};
  constexpr char dr[4] = {'D','R','U','L'};

  constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
  constexpr int INF = 1e9;

  template<class T>
  vector<T> V(int n,T val){
    return vector<T> (n,val);
  }

  template<class T>
  vector<vector<T>> V(int n,int m,T val){
    return vector<vector<T>> (n,vector<T> (m,val));
  }

  template<class T>
  vector<vector<vector<T>>> V(int n,int m,int k,T val){
    return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
  }
}


using namespace IN;
using namespace OUT;
using namespace FUNC;
























signed main(){
  IO();
  
  int n,m,K;
  re(n,m,K);

  vt<vt<int>> buy(n,vt<int>(K+1)),sell(n,vt<int>(K+1));

  fr(i,0,n){
    fr(j,0,K){
      re(buy[i][j],sell[i][j]);
    }
    buy[i][K] = sell[i][K] = 0;
  }

  vt<vt<int>> dis(n,vt<int>(n,INF));

  fr(e,0,m){
    int u,v,w; re(u,v,w);
    --u,--v;
    dis[u][v] = w;
  }

  fr(k,0,n) fr(i,0,n) fr(j,0,n) ckmin(dis[i][j],dis[i][k]+dis[k][j]);

  auto can = [&](int ef) -> bool {
    auto min_dis = V<long long>(n,n,INFLL1);
    fr(i,0,n){
      fr(j,0,n){
        if(dis[i][j] == INF) continue;
        long long best = -INF;
        fr(k,0,K+1){
          if(sell[j][k] < 0 || buy[i][k] < 0) continue;
          ckmax(best,sell[j][k] - buy[i][k] - ef * 1LL * dis[i][j]);
        }
        if(best == -INF) continue;
        ckmin(min_dis[i][j],-best);
      }
    }

    fr(k,0,n) fr(i,0,n) fr(j,0,n) ckmin(min_dis[i][j],min_dis[i][k]+min_dis[k][j]);


    fr(i,0,n) if(min_dis[i][i] <= 0) return true;

    return false;
  };

  int lo = 0, hi = INF;

  while(hi - lo > 1){
    int mid = (hi + lo)/2;
    can(mid) ? lo = mid : hi = mid;
  }

  cout << lo;



  // output_run_time();
  return 0;
}

Compilation message

merchant.cpp: In function 'void FUNC::IO(std::string)':
merchant.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 1228 KB Output is correct
2 Correct 28 ms 340 KB Output is correct
3 Correct 29 ms 436 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 9 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 9 ms 340 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 9 ms 340 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 10 ms 340 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 5 ms 340 KB Output is correct
18 Correct 7 ms 340 KB Output is correct
19 Correct 12 ms 340 KB Output is correct
20 Correct 9 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 9 ms 340 KB Output is correct
23 Correct 17 ms 380 KB Output is correct
24 Correct 8 ms 340 KB Output is correct
25 Correct 17 ms 376 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 12 ms 340 KB Output is correct
28 Correct 13 ms 340 KB Output is correct
29 Correct 11 ms 380 KB Output is correct
30 Correct 5 ms 364 KB Output is correct
31 Correct 6 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 13 ms 340 KB Output is correct
5 Correct 11 ms 380 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 108 ms 520 KB Output is correct
9 Correct 391 ms 2912 KB Output is correct
10 Correct 61 ms 556 KB Output is correct
11 Correct 69 ms 736 KB Output is correct
12 Correct 77 ms 724 KB Output is correct
13 Correct 52 ms 556 KB Output is correct

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 14 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 12 ms 340 KB Output is correct
12 Correct 9 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 9 ms 340 KB Output is correct
15 Correct 17 ms 380 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 108 ms 520 KB Output is correct
18 Correct 391 ms 2912 KB Output is correct
19 Correct 61 ms 556 KB Output is correct
20 Correct 69 ms 736 KB Output is correct
21 Correct 77 ms 724 KB Output is correct
22 Correct 52 ms 556 KB Output is correct
23 Correct 17 ms 376 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 12 ms 340 KB Output is correct
26 Correct 13 ms 340 KB Output is correct
27 Correct 11 ms 380 KB Output is correct
28 Correct 5 ms 364 KB Output is correct
29 Correct 6 ms 340 KB Output is correct
30 Correct 263 ms 1228 KB Output is correct
31 Correct 28 ms 340 KB Output is correct
32 Correct 29 ms 436 KB Output is correct
33 Correct 5 ms 340 KB Output is correct
34 Correct 5 ms 340 KB Output is correct
35 Correct 4 ms 340 KB Output is correct
36 Correct 9 ms 340 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 5 ms 340 KB Output is correct
39 Correct 5 ms 340 KB Output is correct
40 Correct 5 ms 340 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 9 ms 340 KB Output is correct
43 Correct 45 ms 468 KB Output is correct
44 Correct 71 ms 596 KB Output is correct
45 Correct 273 ms 1568 KB Output is correct
46 Correct 73 ms 596 KB Output is correct
47 Correct 78 ms 600 KB Output is correct
48 Correct 63 ms 592 KB Output is correct
49 Correct 389 ms 3168 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 38 ms 468 KB Output is correct
53 Correct 41 ms 592 KB Output is correct
54 Correct 42 ms 504 KB Output is correct
55 Correct 41 ms 468 KB Output is correct
56 Correct 31 ms 468 KB Output is correct
57 Correct 0 ms 212 KB Output is correct
58 Correct 13 ms 492 KB Output is correct
59 Correct 12 ms 508 KB Output is correct
60 Correct 10 ms 596 KB Output is correct
61 Correct 464 ms 3424 KB Output is correct
62 Correct 411 ms 3272 KB Output is correct
63 Correct 0 ms 212 KB Output is correct