oj.uz

Submission #106747

# Submission time Handle Problem Language Result Execution time Memory
106747 2019-04-20T09:13:57 Z kig9981 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 39 ms 4344 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<vector<pair<int,int>>> I;
long long D[500][500], C[500][500];

long long comp(long long u1, long long d1, long long u2, long long d2)
{
	return u1*d2-u2*d1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, K;
	long long a1=0, a2=1;
	cin>>N>>M>>K;
	I.resize(N);
	memset(D,0x3f,sizeof(D));
	for(int i=0;i<N;i++) {
		I[i].resize(K);
		for(int k=0;k<K;k++) {
			cin>>I[i][k].first>>I[i][k].second;
			if(I[i][k].first!=-1) {
				for(int j=0;j<i;j++) {
					if(I[j][k].first!=-1) {
						C[i][j]=max(C[i][j],1LL*I[j][k].second-I[i][k].first);
						C[j][i]=max(C[j][i],1LL*I[i][k].second-I[j][k].first);
					}
				}
			}
		}
	}
	while(M--) {
		int a, b, w;
		cin>>a>>b>>w; --a; --b;
		D[a][b]=min(D[a][b],1LL*w);
	}
	for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
	for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) {
		if(comp(C[i][j],D[i][j],C[i][k]+C[k][j],D[i][k]+D[k][j])<0) {
			C[i][j]=C[i][k]+C[k][j];
			D[i][j]=D[i][k]+D[k][j];
		}
	}
	for(int i=0;i<N;i++) if(comp(a1,a2,C[i][i],D[i][i])<0) {
		a1=C[i][i];
		a2=D[i][i];
	}
	cout<<a1/a2<<'\n';
	return 0;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2560 KB Output is correct
2 Incorrect 5 ms 2432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2560 KB Output is correct
2 Incorrect 5 ms 2432 KB Output isn't correct
3 Halted 0 ms 0 KB -