oj.uz

Submission #106755

# Submission time Handle Problem Language Result Execution time Memory
106755 2019-04-20T09:52:00 Z kig9981 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 50 ms 3456 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 U[500][500], 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;
			for(int j=0;j<i;j++) {
				if(I[i][k].first!=-1) U[i][j]=C[i][j]=max(C[i][j],1LL*I[j][k].second-I[i][k].first);
				if(I[j][k].first!=-1) U[j][i]=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(D[i][k]==0x3f3f3f3f3f3f3f3f || D[k][j]==0x3f3f3f3f3f3f3f3f) continue;
		if(D[i][j]==0x3f3f3f3f3f3f3f3f || comp(U[i][j],D[i][j],U[i][k]+U[k][j]+C[i][j],D[i][k]+D[k][j])<0) {
			U[i][j]=U[i][k]+U[k][j]+C[i][j];
			D[i][j]=D[i][k]+D[k][j];
		}
	}
	for(int i=0;i<N;i++) if(comp(a1,a2,U[i][i],D[i][i])<0) {
		a1=U[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 50 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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