oj.uz

Submission #106227

# Submission time Handle Problem Language Result Execution time Memory
106227 2019-04-17T13:11:39 Z polyfish Travelling Merchant (APIO17_merchant) C++14
54 / 100
 301 ms 3188 KB 
//Pantyhose(black) + glasses = infinity
 
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "merchant"
 
const int64_t MAX_N = 102;
const int64_t MAX_K = 1002;
const int64_t INF = 1e9+1e8;
const long double _EPS = 1e-8;
 
struct edge {
	int64_t u, v;
	long double w;
 
	edge() {}
 
	edge(int64_t u, int64_t v, long double w): u(u), v(v), w(w) {}
};
 
int64_t n, m, k, b[MAX_N][MAX_K], s[MAX_N][MAX_K], c[MAX_N][MAX_N], mx[MAX_N][MAX_N];
vector<edge> g[MAX_N]; 
long double d[MAX_N];
 
void read_input() {
	cin >> n >> m >> k;
 
	for (int64_t i=1; i<=n; ++i) {
		for (int64_t j=1; j<=k; ++j)
			cin >> b[i][j] >> s[i][j];
	}
}
 
void floyd() {
	for (int64_t i=1; i<=n; ++i) {
		for (int64_t j=1; j<=n; ++j)
			c[i][j] = INF;
	}
 
	for (int64_t i=1; i<=n; ++i)
		c[i][i] = 0;
 
	for (int64_t i=1; i<=m; ++i) {
		int64_t u, v;
		cin >> u >> v;
		cin >> c[u][v];
	}
 
	for (int64_t k=1; k<=n; ++k) {
		for (int64_t i=1; i<=n; ++i) {
			for (int64_t j=1; j<=n; ++j)
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
		}
	}
 
	// debug(c[4][1]);
}
 
void init() {
	for (int64_t i=1; i<=n; ++i) {
		for (int64_t j=1; j<=n; ++j) {
			mx[i][j] = -INF;
 
			for (int64_t t=1; t<=k; ++t) {
				if (b[i][t]!=-1 && s[j][t]!=-1)
					mx[i][j] = max(mx[i][j], -b[i][t] + s[j][t]);
			}
		}
	}
 
	// debug(mx[1][4]);
}
 
bool relax(edge e) {
	if (abs(d[e.v] - d[e.u] - e.w)>_EPS && d[e.v] > d[e.u] + e.w) {
		d[e.v] = d[e.u] + e.w;
		return true;
	}
 
	return false;
}
 
bool check_negative_cycle(long double x) {
	vector<edge> E;
 
	for (int64_t i=1; i<=n; ++i) {
		for (int64_t j=1; j<=n; ++j)
			E.push_back(edge(i, j, x*c[i][j] - max((int64_t)0, mx[i][j])));
	}
 
	memset(d, 0, sizeof(d));
 
	for (int64_t i=0; i<=n; ++i) {
		if (i==n)
			return true;
 
		bool stop = true;
 
		for (auto e : E) {
			if (relax(e))
				stop = false;
		}
 
		if (stop)
			break;
	}
 
	return false;
}
 
long double bisect() {
	long double l = 0, r = INF;
 
	while (abs(l-r)>1e-6) {
		long double mid = (l + r) / 2;
 
		if (check_negative_cycle(mid))
			l = mid;
		else
			r = mid;
	}
 
 	// cerr << setiosflags(ios::fixed) << setprecision(7) << l << '\n';
	return r;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
 
	read_input();
	floyd();
	init();
	// debug(check_negative_cycle(1.9));
	cout << int64_t(bisect());
	// for (int64_t i=1; i<=n; ++i) {
	// 	for (int64_t j=1; j<=n; ++j) {
	// 		if (mx[i][j]==-INF)
	// 			cout << -1 << " \n"[j==n];
	// 		else
	// 			cout << mx[i][j] << " \n"[j==n];
	// 	}
	// }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3024 KB Output is correct
2 Incorrect 102 ms 2216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1116 KB Output is correct
2 Correct 26 ms 1144 KB Output is correct
3 Correct 23 ms 1192 KB Output is correct
4 Correct 23 ms 1148 KB Output is correct
5 Correct 35 ms 1148 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 21 ms 1124 KB Output is correct
8 Correct 32 ms 1188 KB Output is correct
9 Correct 19 ms 1124 KB Output is correct
10 Correct 37 ms 1268 KB Output is correct
11 Correct 39 ms 1148 KB Output is correct
12 Correct 38 ms 1184 KB Output is correct
13 Correct 19 ms 1104 KB Output is correct
14 Correct 28 ms 1160 KB Output is correct
15 Correct 21 ms 1184 KB Output is correct
16 Correct 25 ms 1252 KB Output is correct
17 Correct 28 ms 1192 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 45 ms 1152 KB Output is correct
20 Correct 30 ms 1256 KB Output is correct
21 Correct 26 ms 1188 KB Output is correct
22 Correct 30 ms 1140 KB Output is correct
23 Correct 28 ms 1140 KB Output is correct
24 Correct 9 ms 1136 KB Output is correct
25 Correct 27 ms 1160 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 25 ms 1096 KB Output is correct
28 Correct 27 ms 1152 KB Output is correct
29 Correct 27 ms 1140 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 15 ms 1192 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 2456 KB Output is correct
2 Correct 287 ms 3012 KB Output is correct
3 Correct 201 ms 2540 KB Output is correct
4 Correct 123 ms 2496 KB Output is correct
5 Correct 301 ms 2384 KB Output is correct
6 Correct 151 ms 2280 KB Output is correct
7 Correct 28 ms 1192 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 45 ms 1152 KB Output is correct
10 Correct 30 ms 1256 KB Output is correct
11 Correct 26 ms 1188 KB Output is correct
12 Correct 30 ms 1140 KB Output is correct
13 Correct 28 ms 1140 KB Output is correct

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1116 KB Output is correct
2 Correct 26 ms 1144 KB Output is correct
3 Correct 23 ms 1192 KB Output is correct
4 Correct 23 ms 1148 KB Output is correct
5 Correct 35 ms 1148 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 21 ms 1124 KB Output is correct
8 Correct 32 ms 1188 KB Output is correct
9 Correct 19 ms 1124 KB Output is correct
10 Correct 37 ms 1268 KB Output is correct
11 Correct 39 ms 1148 KB Output is correct
12 Correct 38 ms 1184 KB Output is correct
13 Correct 19 ms 1104 KB Output is correct
14 Correct 28 ms 1160 KB Output is correct
15 Correct 21 ms 1184 KB Output is correct
16 Correct 25 ms 1252 KB Output is correct
17 Correct 159 ms 2456 KB Output is correct
18 Correct 287 ms 3012 KB Output is correct
19 Correct 201 ms 2540 KB Output is correct
20 Correct 123 ms 2496 KB Output is correct
21 Correct 301 ms 2384 KB Output is correct
22 Correct 151 ms 2280 KB Output is correct
23 Correct 28 ms 1192 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 45 ms 1152 KB Output is correct
26 Correct 30 ms 1256 KB Output is correct
27 Correct 26 ms 1188 KB Output is correct
28 Correct 30 ms 1140 KB Output is correct
29 Correct 28 ms 1140 KB Output is correct
30 Correct 87 ms 2316 KB Output is correct
31 Correct 143 ms 2448 KB Output is correct
32 Correct 133 ms 2956 KB Output is correct
33 Correct 173 ms 2440 KB Output is correct
34 Correct 156 ms 2368 KB Output is correct
35 Correct 197 ms 2412 KB Output is correct
36 Correct 188 ms 3188 KB Output is correct
37 Correct 3 ms 512 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 144 ms 2220 KB Output is correct
40 Correct 124 ms 2256 KB Output is correct
41 Correct 130 ms 2364 KB Output is correct
42 Correct 130 ms 2400 KB Output is correct
43 Correct 140 ms 2288 KB Output is correct
44 Correct 2 ms 384 KB Output is correct
45 Correct 23 ms 1388 KB Output is correct
46 Correct 26 ms 1228 KB Output is correct
47 Correct 29 ms 1180 KB Output is correct
48 Correct 218 ms 2964 KB Output is correct
49 Correct 214 ms 3044 KB Output is correct
50 Correct 2 ms 384 KB Output is correct
51 Correct 140 ms 3024 KB Output is correct
52 Incorrect 102 ms 2216 KB Output isn't correct
53 Halted 0 ms 0 KB -