oj.uz

Submission #172020

# Submission time Handle Problem Language Result Execution time Memory
172020 2019-12-30T20:39:09 Z Pajaraja Travelling Merchant (APIO17_merchant) C++17
0 / 100
 196 ms 2168 KB 
#include <bits/stdc++.h>
#define MAXN 107
#define MAXK 1007
using namespace std;
long long bp[MAXN][MAXK],sp[MAXN][MAXK],d[MAXN][MAXN],w[MAXN][MAXN];
double wb[MAXN][MAXN],dist[MAXN],dn[MAXN];
int n,m,a;
void zvonocovek()
{
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++) if(i!=j)
			dist[j]=min(dist[j],dist[i]+wb[i][j]);
}
bool provera(long long k)
{
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) wb[i][j]=d[i][j]-((double)w[i][j])/((double)k)-0.0000001;
	dist[1]=0; 
	for(int i=2;i<=n;i++) dist[i]=1000000000000000;
	for(int i=1;i<=n;i++) zvonocovek();
	for(int i=1;i<=n;i++) dn[i]=dist[i];
	zvonocovek();
	for(int i=1;i<=n;i++) if(dist[i]!=dn[i]) return true;
	return false;
}
long long binarna(long long l, long long r)
{
	if(l==r) return l;
	long long s=(l+r+1)/2;
	if(provera(s)) return binarna(s,r);
	return binarna(l,s-1);
}
int main()
{
	cin>>n>>m>>a;
	for(int i=1;i<=n;i++) for(int j=1;j<=a;j++) cin>>bp[i][j]>>sp[i][j];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=1000000000000000000LL;
	for(int i=1;i<=m;i++)
	{
		int t1,t2; long long t3;
		cin>>t1>>t2>>t3;
		d[t1][t2]=min(d[t1][t2],t3);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++) if(i!=j)
			for(int k=1;k<=a;k++) if(bp[i][k]!=-1 && sp[j][k]!=-1) 
				w[i][j]=max(w[i][j],sp[j][k]-bp[i][k]);
	//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) printf("%d %d %lld %lld\n",i,j,d[i][j],w[i][j]);
	printf("%d",binarna(0,2000000000));
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:52:35: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d",binarna(0,2000000000));
              ~~~~~~~~~~~~~~~~~~~~~^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2168 KB Output is correct
2 Correct 38 ms 1272 KB Output is correct
3 Incorrect 39 ms 1272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Incorrect 11 ms 888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1528 KB Output is correct
2 Correct 196 ms 2168 KB Output is correct
3 Correct 46 ms 1404 KB Output is correct
4 Correct 57 ms 1528 KB Output is correct
5 Incorrect 58 ms 1784 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Incorrect 11 ms 888 KB Output isn't correct
6 Halted 0 ms 0 KB -