oj.uz

Submission #690987

# Submission time Handle Problem Language Result Execution time Memory
690987 2023-01-30T20:08:06 Z amir Travelling Merchant (APIO17_merchant) C++14
33 / 100
 72 ms 3872 KB 
/*
<< in the name of Allah >>
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' 
#define f first
#define s second


const ll maxn = 1e3+5 , maxk = 1e3 + 4 , inf = 1e13 , MX = 1e17 ;
ll n , m , k ;
ll S[maxn][maxk] , B[maxn][maxk] ;
vector<pll > adj[maxn] ;
ll d[maxn][maxn] , f[maxn][maxn] , c[maxn][maxn] , td[maxn][maxn] ;


bool check(ll x){
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ;j < n ; j++){
			ll XX = (inf/x) ;
			if (d[i][j] > XX){
				f[i][j] = inf ;
			}
			else{
				f[i][j] = x*d[i][j]-c[i][j] ;
			}
			td[i][j] = f[i][j] ;
		}
		td[i][i] = 0 ;
	}
	
	for (int cnt = 0 ; cnt < n ; cnt++){
		for (int i = 0 ; i < n; i++){
			for (int j = 0 ; j < n ; j++){
				td[i][j] = min(td[i][j] , (td[i][cnt] + td[cnt][j])) ;
			}
		}
	}
	
	for (int i = 0 ;i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (j == i) continue ;
			if ((td[i][j]+td[j][i]) <= 0){
				return 1 ;
			}
		}
	}
	
	return 0 ;
	
}

int main()
{
    ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;
	
	cin >> n >> m >> k ;
	
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < k ;j++){
			cin >> B[i][j] >> S[i][j] ;
			if (B[i][j] == -1) B[i][j] = inf ;
			if (S[i][j] == -1) S[i][j] = 0-inf ;
		}
	}
	
	for (int i = 0 ; i < m ; i++){
		ll u , v , t ;
		cin >> u >> v >> t ; u-- , v-- ;
		
		adj[u].ps(mp(v , t)) ;
		d[u][v] = t ;
	}
	for (int i = 0 ; i < n; i++){
		for (int j = 0 ; j < n ; j++){
			if (d[i][j]) continue ;
			d[i][j] = inf ;	
		}
		d[i][i] = 0 ;
	}
	
	for (int cnt = 0 ; cnt < n ; cnt++){
		for (int i = 0 ; i < n; i++){
			for (int j = 0 ; j < n ; j++){
				if (d[i][cnt] != inf && d[cnt][j] != inf)
					d[i][j] = min(d[i][j] , (d[i][cnt] + d[cnt][j])) ;
			}
		}
	}
	
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (d[i][j] == inf){
				c[i][j] = 0-inf ;
				continue ;
			}
			c[i][j] = 0 ;
			
			for (int h = 0 ; h < k ; h++){
				//if (S[j][h] == -1 || B[i][h] == -1) continue ;
				c[i][j] = max(c[i][j] , (S[j][h]-B[i][h])) ;
			}
			
		}
	}
	
	if (!check(1)){
		cout << 0 << '\n' ;
		return 0 ;
	}
	
	//cout << check(3) ;
	
	ll l = 1 , r = 1e13 ;
	
	while (l < r-1){
		ll mid = (l+r) / 2 ;
		if (check(mid)){
			l = mid ;
		}
		else {
			r = mid ;
		}
	}
	
	cout << l << '\n' ;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3788 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 46 ms 3092 KB Output is correct
4 Correct 7 ms 1620 KB Output is correct
5 Incorrect 7 ms 1620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1620 KB Output is correct
2 Correct 12 ms 1620 KB Output is correct
3 Incorrect 1 ms 1620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3216 KB Output is correct
2 Correct 72 ms 3872 KB Output is correct
3 Correct 48 ms 3156 KB Output is correct
4 Correct 51 ms 3156 KB Output is correct
5 Correct 50 ms 3220 KB Output is correct
6 Correct 49 ms 3156 KB Output is correct
7 Correct 8 ms 1620 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 8 ms 1692 KB Output is correct
10 Correct 9 ms 1688 KB Output is correct
11 Correct 8 ms 1624 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 7 ms 1620 KB Output is correct

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1620 KB Output is correct
2 Correct 12 ms 1620 KB Output is correct
3 Incorrect 1 ms 1620 KB Output isn't correct
4 Halted 0 ms 0 KB -