Submission #107396

#	Time	Username	Problem	Language	Result	Execution time	Memory
107396		Noam527	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	119 ms	4308 KiB

merchant

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

int n, m, k;
ll B[101][1001], S[101][1001];
ll D[101][101] = {}, W[101][101];
ll d[101][101];
ll dist[101], cnt[101];

bool check(ll x) {
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
		d[i][j] = W[i][j] - x * D[i][j];
	if (OO) {
		cout << "d\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << d[i][j] << " "; cout << '\n';
		}
		cout << '\n';
	}

	for (int i = 0; i < n; i++) dist[i] = cnt[i] = 0;
	for (int iter = 0; iter <= n; iter++) {
		if (OO) {
			cout << "starting iteration " << iter << '\n';
			cout << "d: ";
			for (int i = 0; i < n; i++) cout << dist[i] << " "; cout << '\n';
			cout << "c: ";
			for (int i = 0; i < n; i++) cout << cnt[i] << " "; cout << '\n';
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (i != j) {
					if (make_pair(dist[j], cnt[j]) < make_pair(dist[i] + d[i][j], cnt[i] + 1)) {
						if (iter == n) return true;
						dist[j] = dist[i] + d[i][j];
						cnt[j] = cnt[i] + 1;
					}
				}
			}
	}
	return false;
}

void preprocess() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i != j) {
				for (int x = 0; x < k; x++)
					if (B[i][x] != -1 && S[j][x] != -1)
						W[i][j] = max(W[i][j], S[j][x] - B[i][x]);
			}
	for (int u = 0; u < n; u++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				D[i][j] = min(D[i][j], D[i][u] + D[u][j]);

	if (OO) {
		cout << "W\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << W[i][j] << " "; cout << '\n';
		}
		cout << '\n';
		cout << "D\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << D[i][j] << " "; cout << '\n';
		}
		cout << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++)
			cin >> B[i][j] >> S[i][j];
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		W[i][j] = 0;
		if (i != j) D[i][j] = inf;
	}
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		--u, --v;
		D[u][v] = w;
	}
	preprocess();
	if (OO) {
		check(2);
		return 0;
	}
	ll lo = 0, hi = 1e9 + 3, mid;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (check(mid)) lo = mid;
		else hi = mid - 1;
	}
	finish(lo);
}

Compilation message (stderr)

merchant.cpp: In function 'bool check(ll)':
merchant.cpp:24:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << d[i][j] << " "; cout << '\n';
    ^~~
merchant.cpp:24:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << d[i][j] << " "; cout << '\n';
                                                        ^~~~
merchant.cpp:34:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int i = 0; i < n; i++) cout << dist[i] << " "; cout << '\n';
    ^~~
merchant.cpp:34:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int i = 0; i < n; i++) cout << dist[i] << " "; cout << '\n';
                                                        ^~~~
merchant.cpp:36:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int i = 0; i < n; i++) cout << cnt[i] << " "; cout << '\n';
    ^~~
merchant.cpp:36:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int i = 0; i < n; i++) cout << cnt[i] << " "; cout << '\n';
                                                       ^~~~
merchant.cpp: In function 'void preprocess()':
merchant.cpp:68:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << W[i][j] << " "; cout << '\n';
    ^~~
merchant.cpp:68:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << W[i][j] << " "; cout << '\n';
                                                        ^~~~
merchant.cpp:73:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << D[i][j] << " "; cout << '\n';
    ^~~
merchant.cpp:73:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << D[i][j] << " "; cout << '\n';
                                                        ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34