oj.uz

Submission #231933

# Submission time Handle Problem Language Result Execution time Memory
231933 2020-05-15T11:22:42 Z ruler Travelling Merchant (APIO17_merchant) C++14
0 / 100
 50 ms 760 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 2e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e2 + 5;

int n, m, t, B[N][N], S[N][N], D[N][N], V[N][N];
ll C[N][N];

bool OK(int q) {
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) C[i][j] = 1LL * q * D[i][j] - V[i][j];
	for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j && C[i][j] + C[j][i] <= 0) return true;
	return false;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	memset(D, 63, sizeof D);

	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= t; j++) cin >> B[i][j] >> S[i][j];
	for (int i = 1; i <= m; i++) {
		int v, u, w; cin >> v >> u >> w;
		D[v][u] = min(D[v][u], w);
	}
	for (int i = 1; i <= n; i++) D[i][i] = 0;
	for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= t; k++) if (B[i][k] != -1 && S[j][k] != -1) V[i][j] = max(V[i][j], S[j][k] - B[i][k]);

	int dw = 0, up = INF;
	while (up - dw > 1) {
		int md = (dw + up) >> 1;
		if (OK(md)) dw = md;
		else up = md;
	}
	cout << dw << endl;

	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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