oj.uz

Submission #97211

# Submission time Handle Problem Language Result Execution time Memory
97211 2019-02-14T12:11:22 Z E869120 Travelling Merchant (APIO17_merchant) C++14
21 / 100
 1000 ms 3712 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long N, M, K, B[109][1009], S[109][1009];
long long dist[109][109], V[109][109], D[109][109], col[109]; long double dp[109], e[109][109];
vector<int>G[109], I;

void dfs(int pos) {
	if (col[pos] == 1) return;
	col[pos] = 1;
	for (int i = 0; i < G[pos].size(); i++) dfs(G[pos][i]);
}

bool solve(long double c) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (dist[i][j] == (1LL << 60) || V[i][j] == -(1LL << 60)) { e[i][j] = 1e18; continue; }
			e[i][j] = 1.0L * c * dist[i][j] - 1.0L * V[i][j];
		}
	}
	for (int i = 1; i <= N; i++) dp[i] = (1LL << 60);
	for (int i = 0; i < I.size(); i++) dp[I[i]] = 0;

	for (int i = 1; i <= 4 * N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				dp[k] = min(dp[k], dp[j] + e[j][k]);
			}
		}
	}
	vector<long double>E1; for (int i = 1; i <= N; i++) E1.push_back(dp[i]);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				dp[k] = min(dp[k], dp[j] + e[j][k]);
			}
		}
	}
	vector<long double>E2; for (int i = 1; i <= N; i++) E2.push_back(dp[i]);

	if (E1 == E2) return false;
	return true;
}

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { dist[i][j] = (1LL << 60); D[i][i] = 1; } }
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) cin >> B[i][j] >> S[i][j];
	}
	for (int i = 1; i <= M; i++) {
		long long a1, a2, a3; cin >> a1 >> a2 >> a3;
		dist[a1][a2] = a3;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			long long Benq = 0;
			for (int k = 1; k <= K; k++) {
				if (S[j][k] == -1 || B[i][k] == -1) continue;
				Benq = max(Benq, S[j][k] - B[i][k]);
			}
			if (dist[i][j] != (1LL << 60)) { V[i][j] = Benq; D[i][j] = 1; }
			else V[i][j] = -(1LL << 60);
		}
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (D[i][k] == 1 && D[k][j] == 1) D[i][j] = 1;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) { if (D[i][j] == 1 && D[j][i] == 1) G[i].push_back(j); }
	}
	for (int i = 1; i <= N; i++) {
		if (col[i] == 1) continue;
		I.push_back(i); dfs(i);
	}

	long long L = 1, R = (1LL << 30), MM, maxn = 0;
	for (int i = 0; i < 35; i++) {
		MM = (L + R) / 2;
		bool t = solve(1.0L * MM - 1e-7);
		if (t == true) { L = MM; maxn = max(maxn, MM); }
		else { R = MM; }
	}
	cout << maxn << endl;
	return 0;
}

Compilation message

merchant.cpp: In function 'void dfs(int)':
merchant.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) dfs(G[pos][i]);
                  ~~^~~~~~~~~~~~~~~
merchant.cpp: In function 'bool solve(long double)':
merchant.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I.size(); i++) dp[I[i]] = 0;
                  ~~^~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 3712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1116 KB Output is correct
2 Correct 122 ms 1024 KB Output is correct
3 Correct 135 ms 1024 KB Output is correct
4 Correct 121 ms 1144 KB Output is correct
5 Correct 150 ms 1024 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 123 ms 1024 KB Output is correct
8 Correct 133 ms 1144 KB Output is correct
9 Correct 140 ms 1144 KB Output is correct
10 Correct 126 ms 1024 KB Output is correct
11 Correct 122 ms 1024 KB Output is correct
12 Correct 127 ms 1144 KB Output is correct
13 Correct 134 ms 1144 KB Output is correct
14 Correct 130 ms 1024 KB Output is correct
15 Correct 136 ms 1152 KB Output is correct
16 Correct 129 ms 1064 KB Output is correct
17 Correct 124 ms 1144 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 147 ms 1024 KB Output is correct
20 Correct 123 ms 1024 KB Output is correct
21 Correct 132 ms 1024 KB Output is correct
22 Correct 151 ms 1116 KB Output is correct
23 Correct 133 ms 1008 KB Output is correct
24 Correct 124 ms 1020 KB Output is correct
25 Correct 154 ms 1092 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 128 ms 1024 KB Output is correct
28 Correct 138 ms 1024 KB Output is correct
29 Correct 133 ms 1116 KB Output is correct
30 Correct 4 ms 512 KB Output is correct
31 Correct 133 ms 1024 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 2004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1116 KB Output is correct
2 Correct 122 ms 1024 KB Output is correct
3 Correct 135 ms 1024 KB Output is correct
4 Correct 121 ms 1144 KB Output is correct
5 Correct 150 ms 1024 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 123 ms 1024 KB Output is correct
8 Correct 133 ms 1144 KB Output is correct
9 Correct 140 ms 1144 KB Output is correct
10 Correct 126 ms 1024 KB Output is correct
11 Correct 122 ms 1024 KB Output is correct
12 Correct 127 ms 1144 KB Output is correct
13 Correct 134 ms 1144 KB Output is correct
14 Correct 130 ms 1024 KB Output is correct
15 Correct 136 ms 1152 KB Output is correct
16 Correct 129 ms 1064 KB Output is correct
17 Execution timed out 1048 ms 2004 KB Time limit exceeded
18 Halted 0 ms 0 KB -