oj.uz

Submission #390331

# Submission time Handle Problem Language Result Execution time Memory
390331 2021-04-15T20:42:05 Z oleksg Robot (JOI21_ho_t4) C++11
100 / 100
 1148 ms 84376 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

struct Edge {
	int to, c;
	ll p;
};

map<int, vector<Edge>> graph[100001];
ll dp[100001];
map<int, ll> dp2[100001], psum[100001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		ll p;
		cin >> u >> v >> c >> p;
		graph[u][c].push_back({v, c, p});
		graph[v][c].push_back({u, c, p});
		psum[u][c] += p;
		psum[v][c] += p;
	}

	memset(dp, 0x3f, sizeof dp);
	dp[1] = 0;
	priority_queue<tuple<ll, int, int>> pq;
	pq.push({0, 1, 0});
	while (pq.size()) {
		ll cost;
		int node, c;
		tie(cost, node, c) = pq.top();
		pq.pop();

		if (c) {
			if (dp2[node][c] != -cost) continue;
			for (Edge i : graph[node][c]) {
				// We can't flip i in this case
				ll case1 = psum[node][c] - i.p;
				if (case1 - cost < dp[i.to]) {
					dp[i.to] = case1 - cost;
					pq.push({-dp[i.to], i.to, 0});
				}
			}
		} else {
			if (dp[node] != -cost) continue;
			for (auto& i : graph[node]) {
				for (Edge j : i.second) {
					// Case 1: We don't flip j
					ll case1 = psum[node][j.c] - j.p - cost;
					if (case1 < dp[j.to]) {
						dp[j.to] = case1;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Case 2: We flip j but not another edge of the same colour
					ll case2 = j.p - cost;
					if (case2 < dp[j.to]) {
						dp[j.to] = case2;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Case 3: We flip j and another edge of the same colour
					ll case3 = -cost;
					if (!dp2[j.to].count(j.c) || case3 < dp2[j.to][j.c]) {
						dp2[j.to][j.c] = case3;
						pq.push({-dp2[j.to][j.c], j.to, j.c});
					}
				}
			}
		}
	}
	cout << (dp[n] > INF ? -1 : dp[n]);
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 10 ms 15180 KB Output is correct
5 Correct 10 ms 15180 KB Output is correct
6 Correct 10 ms 15180 KB Output is correct
7 Correct 11 ms 15360 KB Output is correct
8 Correct 10 ms 15196 KB Output is correct
9 Correct 14 ms 15820 KB Output is correct
10 Correct 15 ms 15652 KB Output is correct
11 Correct 12 ms 15516 KB Output is correct
12 Correct 12 ms 15512 KB Output is correct
13 Correct 12 ms 15480 KB Output is correct
14 Correct 12 ms 15436 KB Output is correct
15 Correct 11 ms 15436 KB Output is correct
16 Correct 12 ms 15440 KB Output is correct
17 Correct 13 ms 15472 KB Output is correct
18 Correct 11 ms 15308 KB Output is correct
19 Correct 12 ms 15308 KB Output is correct
20 Correct 12 ms 15472 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 33504 KB Output is correct
2 Correct 97 ms 24720 KB Output is correct
3 Correct 261 ms 29724 KB Output is correct
4 Correct 134 ms 27368 KB Output is correct
5 Correct 1114 ms 78744 KB Output is correct
6 Correct 801 ms 71976 KB Output is correct
7 Correct 428 ms 56352 KB Output is correct
8 Correct 478 ms 50876 KB Output is correct
9 Correct 498 ms 50908 KB Output is correct
10 Correct 371 ms 48184 KB Output is correct
11 Correct 159 ms 32728 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15180 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 10 ms 15180 KB Output is correct
5 Correct 10 ms 15180 KB Output is correct
6 Correct 10 ms 15180 KB Output is correct
7 Correct 11 ms 15360 KB Output is correct
8 Correct 10 ms 15196 KB Output is correct
9 Correct 14 ms 15820 KB Output is correct
10 Correct 15 ms 15652 KB Output is correct
11 Correct 12 ms 15516 KB Output is correct
12 Correct 12 ms 15512 KB Output is correct
13 Correct 12 ms 15480 KB Output is correct
14 Correct 12 ms 15436 KB Output is correct
15 Correct 11 ms 15436 KB Output is correct
16 Correct 12 ms 15440 KB Output is correct
17 Correct 13 ms 15472 KB Output is correct
18 Correct 11 ms 15308 KB Output is correct
19 Correct 12 ms 15308 KB Output is correct
20 Correct 12 ms 15472 KB Output is correct
21 Correct 231 ms 33504 KB Output is correct
22 Correct 97 ms 24720 KB Output is correct
23 Correct 261 ms 29724 KB Output is correct
24 Correct 134 ms 27368 KB Output is correct
25 Correct 1114 ms 78744 KB Output is correct
26 Correct 801 ms 71976 KB Output is correct
27 Correct 428 ms 56352 KB Output is correct
28 Correct 478 ms 50876 KB Output is correct
29 Correct 498 ms 50908 KB Output is correct
30 Correct 371 ms 48184 KB Output is correct
31 Correct 159 ms 32728 KB Output is correct
32 Correct 151 ms 29152 KB Output is correct
33 Correct 175 ms 29896 KB Output is correct
34 Correct 462 ms 50608 KB Output is correct
35 Correct 335 ms 41804 KB Output is correct
36 Correct 377 ms 46832 KB Output is correct
37 Correct 434 ms 49188 KB Output is correct
38 Correct 399 ms 55616 KB Output is correct
39 Correct 163 ms 32500 KB Output is correct
40 Correct 484 ms 52140 KB Output is correct
41 Correct 533 ms 52416 KB Output is correct
42 Correct 598 ms 60740 KB Output is correct
43 Correct 248 ms 37524 KB Output is correct
44 Correct 560 ms 43344 KB Output is correct
45 Correct 365 ms 47484 KB Output is correct
46 Correct 330 ms 47896 KB Output is correct
47 Correct 390 ms 49052 KB Output is correct
48 Correct 1148 ms 84376 KB Output is correct