oj.uz

Submission #201504

# Submission time Handle Problem Language Result Execution time Memory
201504 2020-02-10T19:30:54 Z Noam527 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 63 ms 3684 KB 
#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e16;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct edge {
	int v, w, i;
	edge() {}
	edge(int vv, int ww, int ii) {
		v = vv;
		w = ww;
		i = ii;
	}
	bool operator < (const edge &a) const {
		return w > a.w;
	}
};

int n, m;
vector<pair<int, int>> e;
vector<int> c, d;
vector<vector<edge>> g;
vector<ll> cost;

vector<int> dist, to;
vector<int> path1, path2;
vector<int> P1, P2; // P1[i] == j if edge i is used as the jth edge (1-indexed), 0 otherwise

// floyd warshall; normal, without p1, without p2
int fw[202][202], fwp1[202][202], fwp2[202][202];

vector<int> dijkstra(int s, int t) {
	for (auto &i : dist)
		i = -1;
	priority_queue<edge> q;
	q.push(edge(s, 0, -1));
	while (q.size()) {
		edge x = q.top();
		q.pop();
		if (dist[x.v] != -1) continue;
		dist[x.v] = x.w;
		to[x.v] = x.i;
		for (const auto &i : g[x.v])
			if (dist[i.v] == -1)
				q.push(edge(i.v, x.w + i.w, i.i));
	}
	if (dist[t] == -1) return{};
	vector<int> res;
	int cur = t;
	while (cur != s) {
		res.push_back(to[cur]);
		cur = e[to[cur]].first;
	}
	reverse(res.begin(), res.end());
	return res;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	e.resize(m), c.resize(m), d.resize(m);
	g.resize(n);
	cost.resize(m, 0);
	dist.resize(n), to.resize(n);
	P1.resize(m, 0), P2.resize(m, 0);

	for (int i = 0; i < m; i++) {
		cin >> e[i].first >> e[i].second >> c[i] >> d[i];
		e[i].first--, e[i].second--;
		g[e[i].first].push_back(edge(e[i].second, c[i], i));
	}

	path1 = dijkstra(0, n - 1), path2 = dijkstra(n - 1, 0);
	for (int i = 0; i < path1.size(); i++)
		P1[path1[i]] = i + 1;
	for (int i = 0; i < path2.size(); i++)
		P2[path2[i]] = i + 1;

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		if (i != j)
			fw[i][j] = fwp1[i][j] = fwp2[i][j] = md;
		else
			fw[i][j] = fwp1[i][j] = fwp2[i][j] = 0;
	}
	for (int i = 0; i < m; i++) {
		fw[e[i].first][e[i].second] = min(fw[e[i].first][e[i].second], c[i]);
		if (!P1[i])
			fwp1[e[i].first][e[i].second] = min(fwp1[e[i].first][e[i].second], c[i]);
		if (!P2[i])
			fwp2[e[i].first][e[i].second] = min(fwp2[e[i].first][e[i].second], c[i]);
	}
	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
		fwp1[i][j] = min(fwp1[i][j], fwp1[i][k] + fwp1[k][j]);
		fwp2[i][j] = min(fwp2[i][j], fwp2[i][k] + fwp2[k][j]);
	}

	if (OO) {
		cout << "fw\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
		}
		cout << "fwp1\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
		}
		cout << "fwp2\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
		}
		cout << "path1:\n";
		for (const auto &i : path1) cout << i << " "; cout << '\n';
		cout << "path2:\n";
		for (const auto &i : path2) cout << i << " "; cout << '\n';
	}

	// costs for path 1
	for (int i = 0; i < m; i++) {
		int u = e[i].first, v = e[i].second;
		if (!P1[i]) {
			if (fw[0][v] == md || fw[u][n - 1] == md) {
				if (fw[0][n - 1] == md)
					cost[i] += inf;
				else
					cost[i] += fw[0][n - 1];
			}
			else if (fw[0][n - 1] == md)
				cost[i] += fw[0][v] + c[i] + fw[u][n - 1];
			else
				cost[i] += min(fw[0][n - 1], fw[0][v] + c[i] + fw[u][n - 1]);
		}
		else {
			int best = md;
			for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r < path1.size(); r++) {
				u = e[path1[l]].first, v = e[path1[r - 1]].second;
				if (fw[0][u] != md && fwp1[u][v] != md && fw[v][n - 1] != md)
					best = min(best, fw[0][u] + fwp1[u][v] + fw[v][n - 1]);
			}
			if (best == md)
				cost[i] += inf;
			else
				cost[i] += best;
		}
	}

	// same thing for path 2
	for (int i = 0; i < m; i++) {
		int u = e[i].first, v = e[i].second;
		if (!P2[i]) {
			if (fw[n - 1][v] == md || fw[u][0] == md) {
				if (fw[n - 1][0] == md)
					cost[i] += inf;
				else
					cost[i] += fw[n - 1][0];
			}
			else if (fw[n - 1][0] == md)
				cost[i] += fw[n - 1][v] + c[i] + fw[u][0];
			else
				cost[i] += min(fw[n - 1][0], fw[n - 1][v] + c[i] + fw[u][0]);
		}
		else {
			int best = md;
			for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r < path2.size(); r++) {
				u = e[path2[l]].first, v = e[path2[r - 1]].second;
				if (fw[n - 1][u] != md && fwp2[u][v] != md && fw[v][0] != md)
					best = min(best, fw[n - 1][u] + fwp2[u][v] + fw[v][0]);
			}
			if (best == md)
				cost[i] += inf;
			else
				cost[i] += best;
		}
	}

	ll ans = inf;
	if (fw[0][n - 1] != md && fw[n - 1][0] != md)
		ans = min(ans, (ll)fw[0][n - 1] + fw[n - 1][0]);
	for (int i = 0; i < m; i++)
		ans = min(ans, cost[i] + d[i]);
	if (ans > 2 * md)
		cout << "-1\n";
	else
		cout << ans << '\n';
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path1.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path2.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:106:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:106:57: 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 << fw[i][j] << " "; cout << '\n';
                                                         ^~~~
ho_t4.cpp:110:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:110:59: 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 << fwp1[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:114:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:114:59: 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 << fwp2[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:117:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path1) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:117:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path1) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:119:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path2) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:119:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path2) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:139:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r < path1.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~
ho_t4.cpp:168:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r < path2.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 888 KB Output is correct
2 Correct 26 ms 760 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Correct 27 ms 1016 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 25 ms 764 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 36 ms 888 KB Output is correct
11 Correct 34 ms 888 KB Output is correct
12 Correct 34 ms 1016 KB Output is correct
13 Correct 26 ms 888 KB Output is correct
14 Correct 27 ms 892 KB Output is correct
15 Correct 27 ms 888 KB Output is correct
16 Correct 27 ms 888 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3552 KB Output is correct
2 Correct 58 ms 3556 KB Output is correct
3 Correct 63 ms 3676 KB Output is correct
4 Correct 27 ms 888 KB Output is correct
5 Correct 30 ms 1016 KB Output is correct
6 Correct 26 ms 888 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 888 KB Output is correct
2 Correct 26 ms 760 KB Output is correct
3 Correct 45 ms 2812 KB Output is correct
4 Correct 26 ms 888 KB Output is correct
5 Correct 51 ms 3544 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 49 ms 3516 KB Output is correct
9 Correct 49 ms 3476 KB Output is correct
10 Correct 53 ms 3684 KB Output is correct
11 Correct 53 ms 3424 KB Output is correct
12 Correct 53 ms 3564 KB Output is correct
13 Incorrect 5 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 888 KB Output is correct
2 Correct 26 ms 760 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Correct 27 ms 1016 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 25 ms 764 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 36 ms 888 KB Output is correct
11 Correct 34 ms 888 KB Output is correct
12 Correct 34 ms 1016 KB Output is correct
13 Correct 26 ms 888 KB Output is correct
14 Correct 27 ms 892 KB Output is correct
15 Correct 27 ms 888 KB Output is correct
16 Correct 27 ms 888 KB Output is correct
17 Correct 61 ms 3552 KB Output is correct
18 Correct 58 ms 3556 KB Output is correct
19 Correct 63 ms 3676 KB Output is correct
20 Correct 27 ms 888 KB Output is correct
21 Correct 30 ms 1016 KB Output is correct
22 Correct 26 ms 888 KB Output is correct
23 Correct 25 ms 888 KB Output is correct
24 Incorrect 5 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -