oj.uz

Submission #244930

# Submission time Handle Problem Language Result Execution time Memory
244930 2020-07-05T09:38:56 Z rrrr10000 Travelling Merchant (APIO17_merchant) C++14
0 / 100
 141 ms 2168 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
int main(){
    ll n,m,k;cin>>n>>m>>k;
    vvi v(n,vi(k*2));
    rep(i,n)rep(j,k*2)cin>>v[i][j];
    vvi val(n,vi(n));
    rep(i,n)rep(j,n){
        rep(t,k)if(v[j][t*2+1]!=-1&&v[i][t*2]!=-1)chmax(val[i][j],v[j][t*2+1]-v[i][t*2]);
    }
    vvi dis(n,vi(n,inf));
    rep(i,m){
        ll a,b;cin>>a>>b>>dis[a-1][b-1];
    }
    rep(i,n)dis[i][i]=0;
    rep(t,n)rep(i,n)rep(j,n)chmin(dis[i][j],dis[i][t]+dis[t][j]);
    // outvv(dis);outvv(val);
    ll ok=0,ng=1000000005;
    while(ng-ok>1){
        ll md=(ok+ng)/2;
        bool able=false;
        vi dp(n);
        vvi f(n,vi(n,inf));
        rep(i,n)f[i][i]=0;
        rep(i,n)rep(j,n)if(inf/md>dis[i][j])chmin(f[i][j],md*dis[i][j]-val[i][j]);
        rep(t,n)rep(i,n)rep(j,n)chmin(f[i][j],f[i][t]+f[t][j]);
        rep(i,n)rep(j,n)if(i!=j)if(f[i][j]+f[j][i]<=0)able=true;
        if(able)ok=md;
        else ng=md;
    }
    out(ok);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 2168 KB Output is correct
2 Correct 34 ms 512 KB Output is correct
3 Incorrect 37 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 18 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 10 ms 384 KB Output is correct
8 Correct 11 ms 384 KB Output is correct
9 Correct 11 ms 384 KB Output is correct
10 Correct 11 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct
12 Correct 15 ms 512 KB Output is correct
13 Incorrect 12 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 18 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 10 ms 384 KB Output is correct
8 Correct 11 ms 384 KB Output is correct
9 Correct 11 ms 384 KB Output is correct
10 Correct 11 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct
12 Correct 15 ms 512 KB Output is correct
13 Incorrect 12 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -